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$.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ But you divide by $n+3$. That reduces the exponent of $n$ by one. $\endgroup$– Daniel FischerJul 31, 2014 at 18:54
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
4
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}$
-
$\begingroup$ Would you mind showing me how to divide this? $\endgroup$– JakeJul 31, 2014 at 18:57
-
2
-
$\begingroup$ @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$. $\endgroup$– joeAJul 31, 2014 at 21:16
-
$\begingroup$ 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. $\endgroup$– amWhyAug 1, 2014 at 11:05
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
$$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$$
$\begingroup$
$\endgroup$
$$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)$$
$\begingroup$
$\endgroup$
$$ \frac{n(n+1)(n+2)}{n+3} = \frac{\Theta(n^3)}{\Theta(n)} = \Theta(n^2)$$