análise de tempo de execução

Então eu sei que $\log^*$ significa logaritmo iterado, então $\log^*(3)$ = $(\log\log\log\log...)$ até $n \leq 1$.

Estou tentando resolver o seguinte:

é

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

pouco $o$, pouco $\omega$ou $\Theta$ do

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

Em termos das funções interiores, $\log^*(2^{2^n})$ é muito maior que $\log^*(n)$, mas esquadrando o $\log^*(n)$ está me jogando fora.

Eu sei disso $\log(n)^2$ é $O(n)$, mas não acho que essa propriedade seja válida para o logaritmo iterativo.

Tentei aplicar o método mestre, mas estou tendo problemas com as propriedades de um $\log^*(n)$função. Tentei definir n como max (ou seja,$n = 5$), mas isso realmente não simplificou o problema.

Alguém tem alguma dica de como devo abordar isso?

Lembre-se de que, para $k > 1$, por definição, temos $\log^*k = \log^*(\log{k}) + 1$.

Aplicando a definição duas vezes, vemos que $\log^*(2^{2^n}) = \log^*n + 2$. Agora podemos comparar$\log^*n + 2$ e $(\log^*n)^2$.

Vamos escrever e ver o que temos. Para rastrear o número de logs, eu os assinarei; Eu sei que isso geralmente é básico, se alguém tiver uma idéia melhor, deixe-me saber ou editá-la:

$$\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))) \\ \approx \log_1...\log_{k-2}(n\log_{k-1}(2)) \\ = \log_1...\log_{k-2}(n+\log_{k-1}(2)) \\ \approx \log_1...\log_{k-2}(n) \\ $$ Desde que estamos procurando grandes $n$, Abandonei os termos aditivos $\log(\log(2))\approx-0.3665$ e $\log(2)\approx0.693$.

Isso mostra que se $\log^*(2^{2^n}) = k$, então $log^*(n) \approx k-2$ou combiná-los,

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

O grande-$\Theta$s são idênticos e, como apontado nos comentários, se a base do logaritmo e a potência forem iguais, as equações serão identicamente iguais.