Compara $O(n^{\log n})$ y $O((\log n)^n)$

Question

Quiero comparar $O(n^{\log n})$ y $O((\log n)^n)$ . Usando wolfram alpha puedo calcular el límite y concluir fácilmente. Sin embargo, no encuentro la forma de hacerlo en papel. He pensado en utilizar la función exponencial o el logaritmo pero no ha funcionado.

¿Puede ayudar, por favor?

Answer 1

HINT

Por la forma exponencial se debe obtener

$$\frac{n^{\log n}}{(\log n)^n}=e^{(\log n)^2-n\log(\log n)}$$

y luego utilizarlo para cualquier $a>0$ $$\frac{\log n}{n^a} \to 0$$

Answer 2

Desde $\log$ está aumentando, puede comparar $n^{\log n}$ y $(\log n)^n$ tomando logaritmos.

Tenemos $\log(n^{\log n}) = (\log n)(\log n) = (\log n)^2$

y $\log((\log n)^n) = n \log\log n$ .

Ahora está claro cuál crece más rápido.

Answer 3

Sugerencia $1$ : Mostrar $\pi(n)= \frac{n}{ \ln(n)}$ es creciente (para $n> e$ ).

Sugerencia $2$ : $\pi(n) > \pi( \ln(n))$ .