How to prove $n^2$ is not in $n^3$

Question

How would I go about to prove the simple complexity of $n^2$ is not in O($n^3$)? Also , how would I go about doing this for big Omega and Theta?

Ex. Prove $n^4$ is not in Omega(n^3)??

Answer 1

Actually, we do have $n^4\in\Omega(n^3)$. That is, $$ \exists k>0\exists n_0\forall n>n_0\colon kn^3\le n^4.$$ In fact you can pick $k=1$ and $n_0=1$.

On the other hand assum $n^2\in\Omega(n^3)$. That is, $$ \exists k>0\exists n_0\forall n>n_0\colon kn^3\le n^2.$$ But since $k>0$ we can find $n$ with $n>\frac 1k$ (and at the same time $n>n_0$) and for this obtain the contradiction $kn^3>n^2$.

(I used the complexity theory definiution fo $\Omega$ above; in number theory one uses $\forall n_0\exists n>n_0$ in place of $\exists n_0\forall n>n_0$, but that does not affect the result in the cases considered)