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.

  • $\begingroup$ 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. $\endgroup$
    – hengxin
    Commented Jan 12, 2015 at 8:23
  • $\begingroup$ 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. $\endgroup$ Commented Jan 12, 2015 at 10:43
  • $\begingroup$ possible duplicate of Sorting functions by asymptotic growth $\endgroup$ Commented Jan 12, 2015 at 10:43

1 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?


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.