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

Question

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

Hint: $n^2\le n^3$, for all $n\ge 1$. – vadim123 Jul 06 '14 at 02:45 — vadim123, Jul 06 '14 at 02:45

score 6 · Accepted Answer · answered Jul 06 '14 at 02:45

6

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.

answered Jul 06 '14 at 02:45

what does ∀n mean? – Steve M Jul 06 '14 at 02:51
for all $n$ ... – Jeb Jul 06 '14 at 02:55
70k...right on the mark!! – amWhy Jul 06 '14 at 12:07

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

1 Answers1