Problem Detail: So I know that $log^*$ means iterated logarithm, so $log^*(3)$ = $(loglogloglog…)$ until $n leq 1$. I’m trying to solve the following: is
$log^*(2^{2^n})$
little $o$, little $omega$, or $Theta$ of
${log^*(n)}^2$
In terms of the interior functions, $log^*(2^{2^n})$ is much bigger than $log^*(n)$, but squaring the $log^*(n)$ is throwing me off. I know that $log(n)^2$ is $O(n)$, but I don’t think that property holds for the iterative logarithm. I tried applying the master method, but I’m having trouble with the properties of a $log^*(n)$ function. I tried setting n to be max (i.e. $n = 5$), but this didn’t really simplify the problem. Does anyone have any tips as to how I should approach this?
Asked By : gfppaste
Answered By : Zach Langley
Recall that for $k > 1$, by definition we have $log^*k = log^*(log{k}) + 1$. By applying the definition twice, we see that $log^*(2^{2^n}) = log^*n + 2$. Now we can compare $log^*n + 2$ and $(log^*n)^2$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1339
