enter image description here

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

  • $\begingroup$ (downvoters please comment) $\endgroup$
    – greybeard
    Sep 4, 2022 at 6:35
  • $\begingroup$ Please try to present the "code" as a code block (see post editor help) instead of a pixel raster (how long is that going to stay valid?). $\endgroup$
    – greybeard
    Sep 4, 2022 at 6:37

2 Answers 2


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

  • $\begingroup$ Thank you so much. I think I get it. Is there a specific way to prove it mathematically? I just plugged the number in. $\endgroup$
    – CSStudent
    Sep 5, 2022 at 0:04
  • $\begingroup$ @CSStudent, proof by induction, or cs.stackexchange.com/q/23593/755 $\endgroup$
    – D.W.
    Sep 5, 2022 at 0:38

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


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.