Question: [![enter image description here](https://i.stack.imgur.com/ATgOh.png)](https://i.stack.imgur.com/ATgOh.png)

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: 
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}$?
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$.