So I know that $\log^*$ means iterated logarithm, so $\log^*(3)$ = $(\log\log\log\log...)$ until $n \leq 1$.

I'm trying to solve the following:



little $o$, little $\omega$, or $\Theta$ of


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?


2 Answers 2


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


Let's write it out and see what we get. To track the number of logs, I'll subscript them; I know that's usually base, if anyone has a better idea let me know or edit it in:

$$ \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) \\ $$ Since we're looking for large $n$, I've dropped the additive terms $\log(\log(2))\approx-0.3665$ and $\log(2)\approx0.693$.

This shows that if $\log^*(2^{2^n}) = k$, then $log^*(n) \approx k-2$, or combining these, $$ \log^*(2^{2^n}) \approx \log^*(n)+2 $$

The big-$\Theta$s are identical, and as pointed out in the comments, if the base of the logarithm and the power are the same, the equations are identically equal.

  • 1
    $\begingroup$ By definition $\log^*n = \log^*(\log(n)) + 1$, so your result is immediate. Moreover, $\log^*(2^{2^n})$ and $\log^*(n) + 2$ are exactly equal, not just approximately. $\endgroup$ Apr 18, 2012 at 15:03
  • $\begingroup$ In big-theta, sure. But is there a proof of that for smaller numbers and all bases? $\endgroup$
    – Kevin
    Apr 18, 2012 at 15:16
  • $\begingroup$ Also $\log^*(\log(2^{2^n}))$ is $\log^*(2^n\log(2))$, not "exactly equal" as you say, except in base 2. $\endgroup$
    – Kevin
    Apr 18, 2012 at 15:30
  • $\begingroup$ Point taken; I was assuming logs were base 2. $\endgroup$ Apr 18, 2012 at 15:50
  • $\begingroup$ I understand, as I was a physics major I generally assume base $e$ unless otherwise stated. (CS too, but Physics comes first as far as logs go.) $\endgroup$
    – Kevin
    Apr 18, 2012 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.