# Which of $2^{\log_*n}$ and $\log\log n$ grows faster?

Function 1: $2^{\log_*n}$

Function 2: $\log(\log n)$

The first function is 2 to the log-star of $n$, the second function is log of log of $n$. What I need to know is which one is Big-Omega of the other one, which means, which one grows faster. How can I figure that out? I know the definition of log-star (iterative logarithm) but I don't know how to apply it in order to compare the given functions. Could you guys give some help?

• This is not a formal answer (just as a complement to the answer of @D.W.). However it is worth noting that $\log^{\ast} n$ grows at an extremely slow rate: much slower than the logarithm itself. An often-mentioned numerical example is (from Iterated logarithm (wiki)): For all values of $n$ relevant to counting the running times of algorithms implemented in practice (i.e., $n \le 265536$, which is far more than the atoms in the known universe), the iterated logarithm with base 2 has a value no more than 5. Commented Jan 12, 2015 at 8:23
Consider $n_k=2^{2^{2^{\cdots}}}$, $k$ levels. Then $\log\log n_k = 2^{2^{2^{\cdots}}}$, $k-2$ levels, while $2^{\log^* n_k} = 2^k$. Does this help?