How can we show that if $f(n) = O(n^2)$, then $ f(n) = O(n^3)$

51 Views Asked by At

I'm looking at the 'positive constants' definition, but just not seeing how to go from here to there.

1

There are 1 best solutions below

3
On BEST ANSWER

By definition $f(n)=\mathcal O(n^2)$ if and only if there's $N$ and $C$ such that for all $n\ge N$ we have $|f(n)|\le C n^2$. In this case clearly we have $$\forall n\ge N,\quad |f(n)|\le C n^3$$ so it suffices to take the same constant.