# Is $O(n^2) = O(n^3)$? Prove your answer.

I am not sure how to go about doing this, I know that:

$$O(g(n))=\{f : \exists \ c \ \in \Bbb R_+, \ \exists \ n_0 \in \Bbb N, \ \forall \ n\geq n_0 :f(n) \le c·g(n)\},$$

but how do I go about using this to prove the statement?

Thanks for any help!

-
You need to clarify what you mean by $O(n^2)=O(n^3)$. Do you mean "$O(n^2)$ is the same thing as $O(n^3)$" or "any function that is $O(n^2)$ is $O(n^3)$"? – Max Morin Oct 21 '12 at 14:59

Suppose $f(n)=O(n^{2})$. Then there exists an $N\in\mathbb{N}$ and $c\in\mathbb{R}^{+}$ such that $n\ge N\Rightarrow|f(n)|\le cn^{2}$. But for $n\ge 1$, $n^{2}\le n^{3}$, so $n\ge N\Rightarrow |f(n)|\le cn^{3}$, i.e. $f(n)=O(n^{3})$. That shows that $f=O(n^{2})\Rightarrow f=O(n^{3})$.

-

Hint: You can consider $f(n)=n^3$

-

Hint: Show that the function $n \mapsto n^3$ is in $O(n^3)$ but not in $O(n^2)$.

-

First you need to decide whether you think $O(n^2)=O(n^3)$ or not. If so, you need to show that every $O(n^2)$ function is $O(n^3)$ and vice-versa. But if you think not, then you need to find a function $f$ that is $O(n^2)$ but not $O(n^3)$, or vice-versa.

-