Tiene

Question

Me preguntaron qué $n n^{1/n} =O(n)$ ?

Puedo ver que el lado izquierdo es siempre más grande que la de $n$ pero ¿cómo podríamos demostrar que la igualdad es falsa?

Answer 1

$$\frac{n\sqrt[n]n}n=\sqrt[n]n\xrightarrow[n\to\infty]{}1\implies n\sqrt[n]n=\mathcal O(n)$$

Answer 2

Alternativamente, recordemos que:

$$f(n)=O(g(n)) \iff \lim_{n\to\infty}{\frac{f(n)}{g(n)}} = C \text{ , for some constant } C\ge0$$

Por lo tanto, para ver por qué se $nn^{1/n} = O(n)$, basta observar que:

$$ \lim_{n\to\infty}{\frac{nn^{1/n}}{n}} = \lim_{n\to\infty}{n^{1/n}} = \lim_{n\to\infty}{e^{\ln{(n^{1/n})}}} = e^{\lim_{n\to\infty}{(\ln{n})/n}} = e^{\lim_{n\to\infty}{(1/n)/1}} = e^{0} = 1 \ge 0 $$

mediante el uso de la regla de L'Hospital.