0

If $f_1(n) \in \Theta(g(n))$ and $f_2(n) \in \Theta(g(n))$, then $f_1(n) - f_2(n) \in \Theta(g(n))$.

If this is true, prove it. Otherwise, provide a counterexample.

Alright so my understanding is, a big theta operation basically means the complexity is equal? like with the formula, it can't be over or under therefore has to be in the middle, my question is how do I sole this question with no algorithm or equation?

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87
Notthesmartest
  • 5
  • It seems you have repeated the $\Theta$ relations making it hard to read. The first is using MathJax. Why is the second one there? Then, do you have any thoughts on the matter? – Ross Millikan Oct 27 '22 at 08:46
  • is that better? – Notthesmartest Oct 27 '22 at 08:52
  • so if big theta is the exact performance of an algorithm, we have two algorithm f1 and f2. is the question, if these two performance subtract, would it still be an exact performance? – Notthesmartest Oct 27 '22 at 08:55
  • Better, but it would be better with \in giving $\in$ instead of \epsilon, a comma showing the first two are the assumptions, and even a line break from \ to separate the desired conclusion. Think about your reader and compare with texts you have seen. It is incorrect to think of $\Theta$ as a class of exact performance as it is only about the leading term and up to a multiplicative factor. Suppose $f1$ and $f2$ are polynomials. Does the conclusion hold? – Ross Millikan Oct 27 '22 at 08:56
  • ok, so lets say we make up two polynomials and take the highest number, ei. X^2 and x^3 in the other polynomial. That's where is get lost because it wouldn't do anything if we just subtract them. – Notthesmartest Oct 27 '22 at 09:05
  • But $x^2$ and $x^3$ are not $\Theta$ of each other or the same thing. Think of polynomials with the same leading term. They are $\Theta$ of each other. – Ross Millikan Oct 27 '22 at 09:09
  • OH true, go that would give me a 0 if they are both x^2 – Notthesmartest Oct 27 '22 at 09:15

0 Answers0