What is the time complexity of the following program

Question

The right answer is Theta(n log logn). But, can someone explain why it is the case? I know intuitively that it is because k is k^2 each time, so it couldn't be (logn) for the second loop. However, what is the actual mathematical analysis that makes it (log logn)?

Answer 1

Hint: If $n=2^{16}$, how many times does the inner loop iterate? Try to work out the exact answer -- I'm sure you can figure it out. What about if $n=2^{32}$? $n=2^{64}$?

Answer 2

The number of iterations of the inner loop can be found by solving the recurrence

$$k_{i+1}=k_i^2,\\k_0=2.$$

Taking the $\lg$, we have

$$\lg k_{i+1}=\lg k_i^2=2\lg k_i,\\\lg k_0=1,$$ which can be readily solved as a geometric progression ($\lg k_i=2^i$).

Alternatively, taking the $\lg\lg$, the recurrence becomes

$$\lg\lg k_{i+1}=\lg\lg k_i^2=\lg(2\lg k_i)=1+\lg\lg k_i,\\\lg\lg k_0=0$$ and the solution is obvisouly

$$\lg\lg k_i=i.$$

Now set $k_i=n$.