¿Por qué es $f(n) =\frac{n(n+1)(n+2)}{(n+3)}$ $O(n^2)$?

Question

Que:

$$f(n) = n(n+1)(n+2)/(n+3)$$

Por lo tanto:

$$f∈O(n^2)$$

¿Sin embargo, no entiendo cómo puede ser $n^2$, no debería ser $n^3$? Si ampliar la parte superior conseguimos $$n^3 + 3n^2 + 2n$$ and the biggest is $n ^ 3 $ not $n ^ 2$.

Answer 1

Pero cuando se divide un polinomio de grado tres,$\,n^3 + 3n^2 + 2n,\,$ por un polinomio de grado uno,$\,n+3,\,$ se termina con un grado dos polinomio$n^2 + 2\;$ con el resto de$\quad \frac{-6}{n+3}$

Answer 2

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

Answer 3

Porque formalmente,$$\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.$ $

Entonces$f\in O(n^2)$ de hecho.

Answer 4

ps

Deje$$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$. Entonces,$f(n)=O(n^2)$

Podríamos elegir, por ejemplo,$\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)}$ y$c=1$.

Por lo tanto, podemos encontrar tales$n_0=1$, por lo tanto:

ps

Answer 5

ps