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!
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!
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.