4 votos

¿Cómo puedo encontrar un $k$ y un $n_0$ ?

Encuentre $k$ tal que

$$(\lg n)^{\lg n}= \Theta (n^k), k \geq 2$$

Eso es lo que he hecho hasta ahora:

$$(\lg n)^{\lg n}=\Theta(n^k) \text{ means that } \exists c_1,c_2>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0: \\ c_1 n^k \leq (\lg n)^{\lg n} \leq c_2n^k$$

¿Cómo puedo continuar?

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.$

0voto

Gudmundur Orn Puntos 853

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.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X