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

Question

Problem

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

---

Attempt at Solution

1. $f(n) = (n+1)(n+2)(n+3)$
2. $g(n) = n^3$

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

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

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

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

7. $(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.

Answer 1

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$$

Answer 2

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.

Answer 3

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.

Answer 4

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