4
$\begingroup$

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$.

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ But you divide by $n+3$. That reduces the exponent of $n$ by one. $\endgroup$ – Daniel Fischer♦ Jul 31 '14 at 18:54
7
$\begingroup$

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}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Would you mind showing me how to divide this? $\endgroup$ – Jake Jul 31 '14 at 18:57
  • 2
    $\begingroup$ See polynomial long division $\endgroup$ – amWhy Jul 31 '14 at 18:59
  • $\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$ – joeA Jul 31 '14 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$ – amWhy Aug 1 '14 at 11:05
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

$$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$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$$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)$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.