Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$ Problem


*

*Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$



Attempt at Solution


*

*$f(n) = (n+1)(n+2)(n+3)$

*$g(n) = n^3$

*Show that there exists an $n_0$ and $C > 0$ such that $f(n) \le Cg(n)$ whenever $n > n_0$

*$f(n) = n^3+6n^2+11n+6 = n^3(1 + 6/n + 11/n^2 + 6/n^3)$

*$f(n) \le C*g(n)$ is

*$n^3(1 + 6/n + 11/n^2 + 6/n^3) \le C*n^3$ is

*$(1 + 6/n + 11/n^2 + 6/n^3) < C$

That's as far as I got.  Should I plug in a value for n to find C?  And then, would that value I plugged in for n be $n_0$?
Any help is appreciated.
Thank you in advance.

You are almost there.
Remember that big-O (and little-O) statements
apply for all large enough $n$,
not for all $n$.
So, in
$(3 + 9/n + 6/n^2) < C$,
give some lower bound for $n$,
say $n > 3$.
Then $9/n < 3$ and
$6/n^2 < 2/3$,
so
$3 + 9/n + 6/n^2 < 3+3+2/3 < 7$,
so $C=7 $ works for $n > 3$.
Note that, as the lower bound for $n$ gets larger
(for example, see what you get for $n = 100$),
the bound on $C$ gets closer to $3$,
its best value.
But it never reaches $3$.
But you only need $a$ bound, not the best bound.
