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.
 A: Your multiplication isn't quite correct. You should get
$$(n + 1)(n + 2)(n + 3) = (n + 1)(n^2 + 5n + 6) = n^3 + 6n^2 + 11n + 6$$
Now proceeding as you did, we get
$$f(n) = n^3 (1 + \frac{6}{n} + \frac{11}{n} + \frac{6}{n^3})$$
Note that if $n \geq 1$, then $1/n \leq 1$; likewise, $1/n^2 \leq 1$ and $1/n^3 \leq 1$. Hence, try choosing 
$$C = 1 + 6 + 11 + 6$$
A: Note that $3+\frac9n+\frac6{n^2}$ decreases as $n$ increases, so you might as well use the smallest possible value of $n$. You can’t use $0$, so take $n=1$: for all $n\ge 1$,
$$3+\frac9n+\frac6{n^2}\le 3+\frac91+\frac6{1^2}=18\;.$$
In other words, if you take $n_0=1$ and $C=18$, you have $|f(n)|\le C|g(n)|$ for all $n\ge n_0$. 
Your definition requires strict inequalities where I have non-strict ones, but that’s easily adjusted for: take $n_0=0$ and $C=19$.
However, your calculation of $f(n)$ can’t be right: $(n+1)(n+2)(n+3)$ does not have $n$ as a factor, and $3n^3+6n^2+9n$ does. I’ll leave it to you to correct the algebraic error and then try to replicate the reasoning above with the corrected expression.
A: 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.
A: If you are not interested in the optimal constant you can notice that for $n \geq 3$, all three terms are smaller than $2n$. This gives $(n+1)(n+2)(n+3) \leq 8n^3$.
