<s>[INST] 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$.
 [/INST] $$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)$$
</s>