# $\log^*(n)$ runtime analysis

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:

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?

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.

• 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. – Zach Langley Apr 18 '12 at 15:03
• In big-theta, sure. But is there a proof of that for smaller numbers and all bases? – Kevin Apr 18 '12 at 15:16
• Also $\log^*(\log(2^{2^n}))$ is $\log^*(2^n\log(2))$, not "exactly equal" as you say, except in base 2. – Kevin Apr 18 '12 at 15:30
• Point taken; I was assuming logs were base 2. – Zach Langley Apr 18 '12 at 15:50
• 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.) – Kevin Apr 18 '12 at 15:58