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

$\endgroup$
1
  • 3
    $\begingroup$ But you divide by $n+3$. That reduces the exponent of $n$ by one. $\endgroup$ Jul 31, 2014 at 18:54

5 Answers 5

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

$\endgroup$
4
  • $\begingroup$ Would you mind showing me how to divide this? $\endgroup$
    – Jake
    Jul 31, 2014 at 18:57
  • 2
    $\begingroup$ See polynomial long division $\endgroup$
    – amWhy
    Jul 31, 2014 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, 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$
    – amWhy
    Aug 1, 2014 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.

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

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

$\endgroup$
0
$\begingroup$

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

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