¿Que es asintóticamente más grande: $\lg(\lg^* n)$ o $\lg^*(\lg n)$?

Question

Esta definición se extrae de "Introducción al Algoritmo, 2ª Edición".

La función logaritmo iterado

Usamos la notación $\lg^* n$ (leer "registro de la estrella de $n$") para denotar el logaritmo iterado, que se define como sigue. Deje $\lg^{(i)} n$ ser definido anteriormente, con $f(n) = \lg n$. Debido a que el logaritmo de un valor no positivo número es indefinido, $\lg^{(i)} n$ está definido sólo si $\lg^{(i-1)} > 0$. Asegúrese de diferenciar $\lg^{(i)}n$ (el logaritmo de la función a aplicar $i$ veces en sucesión, comenzando con el argumento de $n$) $\lg^i n$ (el logaritmo de $n$ elevado a la $i$-ésima potencia). La función logaritmo iterado se define como

$$\lg^* n = \min \{i > 0: \lg^{(i)} n ≤ 1\}$$

El logaritmo iterado es un muy lento crecimiento de la función:

$\lg^* 2 = 1$,

$\lg^* 4 = 2$,

$\lg^* 16 = 3$,

$\lg^* 65536 = 4$,

$\lg^* 265536 = 5$.

En primer lugar, yo no entiendo realmente la definición de $\lg^* n$. No he conocido se definen como $\min \{i = 0: ... \}$. ¿Qué significa eso?

En segundo lugar, según la definición de $\lg^* n$, que es asintóticamente más grande: $\lg(\lg^* n)$ o $\lg^*(\lg n)$?

Answer 1

Which is asymptotically larger: lg(lg* n) or lg*(lg n)?

Yo no podía seguir el CLRS definición de lg* n así que me fui a Wikipedia y vi "[lg* n] es el número de veces que la función logaritmo debe ser aplicado de forma iterativa antes de que el resultado es menor o igual a 1". Cuando traté de que para el ejemplo dado en CLRS, funcionó como se esperaba.

Ahora, puedo ver que si lg* n = i entonces lg*(lg n) = i - 1 puesto de lg*(lg n) es equivalente a otra iteración que significa que necesitaríamos uno menos iteración para obtener el resultado menor o igual a 1 (que es aún más claro mirando a la definición recursiva). Por lo tanto, si lg* n = i, entonces lg*(lg n) = i - 1 y lg(lg* n) = lg(i) para lg*(lg n) es asintóticamente más grande.

Answer 2

El prefijo $\min$ está parado para el mínimo de un conjunto - aquí al parecer es el más pequeño número natural $k$ tal que $\lg^k n \le 1$. Tenga en cuenta que, por definición, $\lg^* 2^m = 1+\lg^*m$, para escribir $n=2^m$ (con el fin de comparar el crecimiento asintótico) reduce las dos cantidades a $\lg(1+\lg^*m)$ la izquierda versus $\lg^*m$ a la derecha, obviamente la derecha crece exponencialmente más rápido.