Formalmente la verificación de que $n \log n = o(n^2)$

Question

Estoy tratando de verificar que $n \log n = o(n^2)$ usando la definición formal de los pequeños-o.

La definición de las pequeñas-o es como sigue

Deje $f$ $g$ funciones $f,g: \mathbb{N} \rightarrow \mathbb R^+$. Decimos que $f(n)=o(g(n))$ si $\lim_{n\to\infty} \frac{f(n)}{g(n)}=0$.

Esto puede ser enunciada como diciendo $f(n)=o(g(n))$ significa que para cualquier número real $c>0$ existen un número $n_0$ donde $f(n) < c \, g(n)$ todos los $n \geq n_0$.

Me gustaría una intuitiva aclaración de la diferencia entre grande y pequeño-o la notación, y se dará una explicación intuitiva de por qué $n \log n = o(n^2)$, así como una prueba formal. Espero que este claro ninguna de mis malos entendidos.

Answer 1

Aquí $f(n) = n \log n$$g(n) = n^2$. (Todos mis logaritmos son a base de $2$, no $e$.) Estamos interesados en la relación $$\frac{f(n)}{g(n)} = \frac{n \log n}{n^2} = \frac{\log n}{n},$$ como $n$ se hace grande. Observe que el numerador crece logarítmicamente, mientras que el denominador crece exponencialmente. Por lo que es intuitivamente claro que esta relación es pequeña (es decir, $o(1)$) $n$ crece grande. Pero que aún debe demostrar rigurosamente.

Un método para hacer esto es el siguiente. En primer lugar, asumir que $n$ es una potencia de $2$. (Nos preocuparemos de un general $n$ después). Es decir, que $n = 2^k$$\log n = k$. Por lo tanto, $$n = 2^k = (1+1)^k \stackrel {()} {=} 1 + k + \binom{k}{2} + \ldots + \binom{k}{k} \geq k + \binom{k}{2} = \frac{k(k+1)}{2} \geq \frac{k^2}{2} = \frac{(\log n)^2}{2}.$$ donde $(a)$ se sigue del teorema del binomio. Por lo tanto, $$\frac{f(n)}{g(n)} = \frac{\log n }{n} \leq \frac{2 \log n}{(\log n)^2} = \frac{2}{\log n}.$$ Así tenemos algunos límite superior en la relación, por lo que estamos en los negocios.

Ahora, corregir los $c > 0$. A continuación, tome $n_0 = 2^{2/c}$. Entonces, si $n \geq n_0$,$\log n \geq \frac{2}{c}$. Por lo tanto, $$\frac{f(n)}{g(n)} \leq \frac{2}{\log n} \leq \frac{2}{(2/c)} = c.$$

Por lo tanto, para cada $c > 0$, existe alguna $n_0$ ($n_0 = 2^{2/c}$ va a trabajar), de tal forma que si $n \geq n_0$, la proporción $\frac{f(n)}{g(n)}$ es en la mayoría de las $c$. Por lo tanto hemos terminado.

Answer 2

$\lim_{n \to \infty} \frac{n \log n}{n^2}=\lim_{n \to \infty} \frac{\log n}{n}=\lim_{n \to \infty} \frac{1}{n}=0$

El último paso es debido al hecho de que tanto el numerador y el denominador tienden a infinito y $n \to \infty$, así que usted puede aplicar L'Hospital de la regla y se diferencian tanto. El límite es de $0$, por lo $f(n)=o(g(n))$.

Más formalmente, por arbitrariamente un gran $n_0, \ n >n_0 \ \exists \ \epsilon>0$ s.t. $\frac{f(n)}{g(n)} < \epsilon$.