How do I find the theta notation for this block?

Question

The block is:

    i=2  
    while(i<n){  
        i=i*i;  
        x=x+1;  
    }  

I need to find the theta notation for how many times x=x+1 executes. I created a table with some sample values but I can't figure out how to move on from there. Here are my sample values:

(n) - (# times looped)  
  3 - 1  
  5 - 2  
 20 - 3  
400 - 4

Answer 1

One way to think about this is to trace through the values of i in your loop. Before the first iteration, the value is 2 = 2¹. After the second iteration, it's 4 = 2². After the third iteration, it's 16 = 2⁴. After the fourth iteration, it's 256 = 2⁸. After the fifth, it's 65,536 = 2¹⁶.

As you can see, after k iterations of the loop, the value of i is 2^2k. This means that the number of iterations will (roughly) correspond to the lowest value of k such that

2^2k ≥ n

Taking the logarithm of both sides twice, we get

2^2k ≥ n

2^k ≥ log₂ n

k ≥ log₂ log₂ n

So the number of loop iterations is roughly log₂ log₂ n. Accordingly, the loop runs O(log log n) times. More precisely, the loop runs Θ(log log n) times, since the loop will not stop until k iterations have elapsed.

Hope this helps!