CODEWITHSUNDEEP
while-looptime-complexity
Saeedeh
Saeedeh

Reputation: 295

Time complexity of this while loop?

What's the time complexity of this loop? 

j=2
while(j <= n)
{
    //body of the loop is Θ(1)
    j=j^2
}

Upvotes: 0

Views: 3859

Answers (1)

Al_th
Al_th

Reputation: 1195

You have 

j = 2

and each loop : j = j^2

The pattern is :

2     = 2^(2^0)
2*2   = 2^(2^1)
4*4   = 2^(2^2)
16*16 = 2^(2^3)

Which can be seen as :

2^(2^k) with k being the number of iteration

Hence loop stops when :

2^(2^k) >= n
log2(2^(2^k)) >= log2(n)
2^k >= log2(n)
log2(2^k) >= log2(n)
k >= log2(log2(n))

the complexity is log2(log2(n))

Upvotes: 3

Related Questions