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$.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityLet:
$$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 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}$
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)$$