Big theta of iterative logarithm

Question

I have two mathematical functions: log(log*n) and 2^(log*n). Now, I want to calculate the asymptotic growth of these two functions(especially I want to find big theta). Finally, I want to compare their complexity. Can anyone please share a formal/intuitive solution that can solve this kind of problems?

Thanks.

Answer 1

This is an interesting one. Let's begin by using a standard technique: it's hard to reason about exponents, so let's take their logarithms instead and see what happens. That leaves us with these functions:

log(log(log* n)) and log* n.

Now the question is how they compare against one another. Generally speaking, the log of some function will always grow more slowly than the function itself, provided that the function keeps growing as it gets bigger. Using the fact that log k < k for all k ≥ 1, if we pick any n ≥ 2²²²² we'll have that log* n ≥ 4, so log log* n ≥ 2, so log log log* n ≤ log* n, which gives us that log log log* n = O(log* n). From there, it's not hard to show that log log* n = O(2^{log* n}).