Me parece que $\ln n$ es un exponente bruto, y por eso quiero simplificar la expresión. Tienes razón cuando dices que queremos encontrar las condiciones para que
$$ c_1 n^k < \ln n ^{\ln n} < c_2 n^k,$$
pero si tomamos registros en todas partes, entonces esto es lo mismo que encontrar condiciones para que
$$\ln c_1 + k \ln n < \ln n (\ln \ln n) < \ln c_2 + k \ln n.$$
Ahora nos encontramos con un problema. Para cualquier $k$ , con el tiempo $\ln \ln n$ va a crecer mucho más que $k$ . Arbitrariamente más grande, incluso. Así que nunca encontraremos las condiciones para que $\ln n (\ln \ln n) < \ln c_2 + k \ln n$ . Nos vemos obligados a concluir que $(\ln n) ^ {\ln n}$ no es $\Theta (n^k)$ para cualquier $k$ .
Y lo que es más interesante, aunque los troncos sean pequeños, el crecimiento exponencial es enorme . Sin embargo, como no ganará hasta $\ln \ln n \gg k$ , se necesitará mucho, mucho tiempo para $(\ln n) ^ {\ln n}$ para alcanzar el crecimiento polinómico inicial.
0 votos
$(\log n)^{\log n} = e^{\log n\log\log n} = n^{\log\log n}$ . Desde $\log\log n$ es ilimitado, no creo que puedas resolver esto, porque no es cierto para cualquier $k$ ...
0 votos
Así que, no podemos ni encontrar un $O$ ¿cierto? Pero podríamos encontrar un $\Omega$ ¿o no?
0 votos
No puedes encontrar un polinomio $O$ no. Wikipedia da dos definiciones para $\Omega.$
0 votos
Con $\Omega$ Quiero decir que la primera desigualdad de la definición anterior se mantiene: $$\exists c>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0: \\ cn^k \leq (\lg n)^{\lg n}$$