$ \ Log ^ * (n) $ análisis de tiempo de ejecución

Question

Así que sé que $ \ log ^ * $ iterados medios logaritmo, por lo que $ \ log ^ * (3) $ = $ (\ log \ log \ log \ log ...) $ hasta $ n \ leq 1 $ .

Estoy tratando de resolver el siguiente:

es

$ \ log ^ * (2 ^ {2 ^ n}) $

pequeño $ O $, poco $ \ omega $, o $ \ theta $ de

$ {\ log ^ * (n)} ^ 2 $

En cuanto a las funciones interiores, $ \ log ^ * (2 ^ {2 ^ n}) $ es mucho más grande que $ \ log ^ * (n) $, pero la cuadratura del $ \ log ^ * (n) $ me está lanzando fuera.

Sé que $ \ log (n) ^ 2 $ $ es O (n) $, pero no creo que la propiedad se mantiene para el logaritmo iterativo.

He intentado aplicar el método maestro, pero estoy teniendo problemas con las propiedades de un $ \ log ^ * (n) $ función. Intenté fijar n a ser como máximo (es decir, $ n = 5 $), pero esto no realmente simplificar el problema.

¿Alguien tiene algún consejo en cuanto a cómo debería abordar esto?

Answer 1

Hay que recordar que para k $> $ 1, por definición, tenemos $ \ log ^ * k = \ log ^ * (\ log {k}) + 1 $.

Mediante la aplicación de la definición dos veces, vemos que $ \ log ^ * (2 ^ {2 ^ n}) = \ log ^ * n + 2 $. Ahora podemos comparar $ \ log ^ * n + 2 $ y $ (\ log ^ * n) ^ 2 $.

Answer 2

escritura de dejarlo salir y ver lo que tenemos. Para realizar el seguimiento del número de registros, voy a subíndice ellos; Sé que es por lo general de base, si alguien tiene una idea mejor que me permiten conocer o editarlo en:

$$ \ Log ^ * (2 ^ {2 ^ n}) \\ = \ Log_1 (\ log_2 (... \ log_k (2 ^ {2 ^ n}) ...)) \\ = \ Log_1 ... \ log_ {k-1} (2 ^ n \ log_ {k} (2)) \\ = \ Log_1 ... \ log_ {k-2} (\ log_ {k-1} (2 ^ n) + \ log_ {k-1} \ log_ {k} (2))) \\ = \ Log_1 ... \ log_ {k-2} (n \ log_ {k-1} (2) + \ log_ {k-1} \ log_ {k} (2))) \\ \ Aprox \ log_1 ... \ log_ {k-2} (n \ log_ {k-1} (2)) \\ = \ Log_1 ... \ log_ {k-2} (n + \ log_ {k-1} (2)) \\ \ Aprox \ log_1 ... \ log_ {k-2} (n) \\ $$ Ya que estamos buscando grandes $ n $, se me ha caído los términos aditivos $ \ log (\ log (2)) \ aprox-0,3665 $ y $ \ log (2) \ approx0.693 $.

Esto muestra que si $ \ log ^ * (2 ^ {2 ^ n}) = K $, entonces $ Log ^ * (n) \ aprox k-2 $, o la combinación de estos, $$ \ Log ^ * (2 ^ {2 ^ n}) \ aprox \ log ^ * (n) 2 $$

La gran -. $ \ Theta $ s son idénticos, y tan fuera de punta en los comentarios, si la base de los logaritmos y el poder son los mismos, las ecuaciones son idénticamente igual