Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$. (Big-o notation)

Question

Will someone help me prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$?

Thank you.

Answer 1

Hint: For all positive integers $n$, your expression is $\le (n+n)(n+2n)(n+3n)$.

Remark: A fancier way of doing the same thing is to show that $$\frac{(n+1)(n+2)(n+3)}{n^3}$$ is bounded above, that is, that there is a constant $C$ such that $\frac{(n+1)(n+2)(n+3)}{n^3}<C$. With some algebra, we find that
$$\frac{(n+1)(n+2)(n+3)}{n^3}=\left(1+\frac{1}{n}\right)\left(1+\frac{2}{n}\right) \left(1+\frac{3}{n}\right).$$ Each term on the right is less than $5$ (we are giving away a lot), so we can take $C=5^3$.

The reason for the fancier approach is that to show that $f(n)=O(g(n))$ it is often useful to concentrate on the ratio $\dfrac{f(n)}{g(n)}$

Answer 2

We have $$(n+1)(n+2)(n+3)\leq (n+3)^3\leq (n+3n)^3=4^3n^3$$ and the other inequality is immediate and you conclude.

Answer 3

The easiest I guess: $$ (n+1)(n+2)(n+3)\leq(n+3)^3 \leq 4n^3=O(n^3) $$ The second inequality is for $n>N$, appropriately selected $N$

Answer 4

Note that,

if $\lim_{n\to \infty} \frac{f(n)}{g(n)}=c $, $c$ is finite, then $f=O(g) $.

In your case, we have

$$ \lim_{n\to \infty} \frac{(n+1)(n+2)(n+3)}{n^3}=1, $$

which implies $ (n+1)(n+2)(n+3)=O(n^3) .$