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

Question

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?

Thank you in advance.

• hengxin: 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.
• David Richerby: Note that functions don't have time complexity. A function is just a map from numbers to numbers and that map can be used to measure any property, such as time complexity, population of an ant colony or Bill Gates's personal fortune. Functions have growth rates, algorithms have running times, problems have time complexity.
• David Richerby: possible duplicate of Sorting functions by asymptotic growth

Answer 1

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?