I'm reading The Algorithm Design Manual and this is one of the excersizes:

Prove or disprove the following statement:

$\Theta(n^2 ) = \Theta(n^2 + 1)$

I think this is untrue because the right side of the equation claims to have a multiple $c$ such that it is smaller than all the multiples of $n^2$, which is untrue. But since the book doesn't have answers and I'm not really sure about this question I had to ask.

Thanks a lot :)


As we have on both sides of equality sets, then it should be prove correspondingly i.e we need to show, that $\Theta(n^2) \subset \Theta(n^2+1)$ and $ \Theta(n^2+1)\subset \Theta(n^2) $. Let's start with first:

Assume $f \in \Theta(n^2)$. This means, that for some constants $A_1, A_2 \gt 0$ holds

$$A_1 n^2 \leqslant f(n) \leqslant A_2 n^2$$. To obtain inequalities for $\Theta(n^2+1)$ we need $$B_1 (n^2+1) \leqslant f(n) \leqslant B_2 (n^2+1)$$ It's easy to see, that it's enough to take $B_2 = A_2$ for right hand and $0<B_1 \leqslant \frac{A_1}{2}\leqslant \frac{A_1 n^2}{n^2+1}$ for left hand, as $A_2>0$.

  • $\begingroup$ Thanks a lot! :) $\endgroup$ – kasra Feb 1 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.