Proof of $\Theta (n^2) + O(n^3) \ne O(n^3)$

Question

This is a homework question. I have proved before that the sum of the terms on the left-hand-side are a subset of $O(n^3)$, but I have not proved that the two terms are not equal (or whether that was a strict subset, as the $\ne$ implies).

I'm not sure how to proceed or how to use my earlier proof or whether not to do so.

Edit: I have an idea of how to proceed, but I'm not sure how to be explicitly correct about it. I can pick a function of higher order than 3 (say, $n^4$) which would be in $\Theta(n^2)$, and say that that is $O(n^4)$. Therefore, $O(n^4) + O(n^3) \ne O(n^3)$.

Edit 2: None of the above edit is correct.

Answer 1

The two sets are, in fact, equal. You have already shown that $\Theta (n^2) + O(n^3) \subseteq O(n^3)$.

To see why $O(n^3) \subseteq \Theta (n^2) + O(n^3)$, choose any $f \in O(n^3)$. Then we know that there exist some constants $C,n_0$ such that for all $n \geq n_0$, we have: $$ f(n) \leq Cn^3 = (n^2) + (Cn^3 - n^2) $$

It should be easy to see that $n^2 \in \Theta(n^2)$ and $Cn^3 - n^2 \in O(n^3)$. Hence, we have $f \in \Theta (n^2) + O(n^3)$, as desired.

Answer 2

The function $f(n)=n^4$ doesn't satisfy $f(n)\in\Theta(n^2)$; I suspect you may be getting $\Theta()$ confused with $\Omega()$.

To see why the inequality doesn't hold (assuming your definition of $O(f(n))$ requires the functions which are members to be positive, which is fairly common), look at the RHS $\Theta(n^2)+O(n^3)$; it's not necessarily true that every function in this set grows as fast as $Cn^3$, but it is the case that every function in this set must grow as fast as $Cn^2$ for some $n$ (since it's the sum of a function $\in\Theta(n^2)$ which grows that fast and a function $\in O(n^3)$ which is positive). Can you think of any functions in $O(n^3)$ which don't grow as fast as $\Theta(n^2)$?