¿Cómo probar que$n\log n = O(n^2)$?

Question

Cómo probar que $n\log n = O(n^2)$?

Creo que tengo la idea, pero necesitan un poco de ayuda a través de la siguiente.

Puedo empezar por demostrar que si $f(n) = n \log n$ $f(n)$ es un miembro de $O(n\log n)$. Para mostrar esto, realizo un gran valor $k$ y muestran que $i\geq k$$f(i) \leq c_1\cdot i\log(i)$.

Lo siguiente que necesita para demostrar que si $f(n)$ es un miembro de $O(n \log n)$ $f(n)$ es un miembro de $O(n^2)$, teniendo un gran valor $k$ y mostrando que $i\geq k$$f(i) \leq c_2\cdot i\log i$, que resulta ser $f(i)=i^2\log i$ que es un miembro de $O(n^2)$.

Es ese derecho? Podría alguien formalizar esto para mí?

Answer 1

Desde su notación, parece que estamos suponiendo que la $n\in\mathbb{N}$. De hecho, voy a ser más general y acaba de decir $n\in(0,\infty)$.

A continuación,$\log n<n$, ya que el $n < 1+n < e^n$ por su serie de Taylor.

Por lo tanto, $n\log n<n^2$ todos los $n\in(0,\infty)$.

Como consecuencia, $n\log n = O(n^2)$.

Answer 2

Sugerencias:

$$\frac{n\log n}{n^2}=\frac{\log n}n\stackrel{\text{l'Hospital, for ex.}}{\xrightarrow[n\to\infty]{}0}$$

Answer 3

Usted sólo tiene que probar la primera parte. Cuando usted escribe $f = O(g)$ que realmente significan $f \in O(g)$. Para demostrar que la primera parte debe demostrar que $$\limsup \frac fg < +\infty$$ y en este caso la que realmente tiene $$\lim \frac fg = 0$$ por lo tanto se cumple con la condición.