# What is the time complexity of the following program

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

• (downvoters please comment) Sep 4, 2022 at 6:35
• 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?). Sep 4, 2022 at 6:37

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

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

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