Why is $f(n) =\frac{n(n+1)(n+2)}{(n+3)}$ in $O(n^2)$?

Let:

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

Therefore :

$$f∈O(n^2)$$

However, I don't understand how it could be $n^2$, shouldn't it be $n^3$? If I expand the top we get $$n^3 + 3n^2 + 2n$$ and the biggest is $n^3$ not $n^2$.

• But you divide by $n+3$. That reduces the exponent of $n$ by one. – Daniel Fischer Jul 31 '14 at 18:54

But when you divide a degree-three polynomial, $\,n^3 + 3n^2 + 2n,\,$ by a degree-one polynomial, $\,n+3,\,$ you end up with a degree two polyonomial $n^2 + 2\;$ with remainder of $\quad \frac{-6}{n+3}$

• Would you mind showing me how to divide this? – Jake Jul 31 '14 at 18:57
• – Namaste Jul 31 '14 at 18:59
• @Jake In practice, though, I don't think you'd actually do the division. I just note that the constants are insignificant in the limit so I drop them, leaving me $\frac{n^3}{n}$ which trivially reduces to $n^2$. – joeA Jul 31 '14 at 21:16
• True, @joeA But given the OP isn't familiar with how to perform polynomial long division, or that you can cancel degrees from numerator and denominator, it's a good time to learn how. – Namaste Aug 1 '14 at 11:05

Because formally, $$\lim_{n \to \infty} \left | \frac{f(x)}{g(x)} \right |= \lim_{n \to \infty} \left | \frac{\frac{n(n+1)(n+2)}{n+3}}{n^2} \right |= \lim_{n \to \infty} \left | \frac{n(n+1)(n+2)}{n^2(n+3)} \right | = 1.$$

So $f\in O(n^2)$ indeed.

$$n+2\leqslant n+3\implies f(n)\leqslant n(n+1)=n^2+n\leqslant2n^2$$ $$(n+1)(n+2)=n(n+3)+2\geqslant n(n+3)\implies f(n)\geqslant n^2$$

$$f(n)=\frac{n(n+1)(n+2)}{n+3}=\frac{(n^2+n)(n+2)}{n+3}=\frac{n^3+2n^2+n^2+2n}{n+3}=\frac{n^3+3n^2+2n}{n+3} \\ =n^2-\frac{6}{n+3}+2$$

Let $f(n)=O(n^2)$.Then, $\exists c>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0: \\ f(n) \leq cn^2 \Rightarrow n^2-\frac{6}{n+3}+2 \leq cn^2 \Rightarrow c \geq 1+\frac{2}{n^2}-\frac{6}{n^2(n+3)}$

We could pick for example $c=1$ and $n_0=1$.

Therefore,we can find such $c,n_0$,therefore:

$$f(n)=O(n^2)$$

$$\frac{n(n+1)(n+2)}{n+3} = \frac{\Theta(n^3)}{\Theta(n)} = \Theta(n^2)$$