I'm working on a homework problem that asks to prove that $Θ(n)+O(n^2 )≠O(n^2 )$.
I'm not looking for an answer to the problem, just a better understanding of what it is that needs to be proved.
The previous question in the homework had me prove $Θ(n)+O(n^2 )⊆O(n^2 )$, which I feel I have successfully done. So how does one go from proving that $Θ(n)+O(n^2 )$ is a subset of $O(n^2 )$ to proving $Θ(n)+O(n^2 )≠O(n^2 )$?
You must show that $O(n^2)$ is not a subset of $\Theta(n) + O(n^2)$. So you need to find a function that is $O(n^2)$ but not $\Theta(n) + O(n^2).$ A helpful thing to remember is that in $O(n^2),$ $n^2$ is allowed to overestimate the growth (it is an upper bound), but not in the case of $\Theta(n).$ If $f(n)\in\Theta(n),$ $n$ must be its true asymptotic growth.