Calicut Gate Academy Test Series | DAA Find Complexity

Question

Complexity of the below code snippet is ..

for (i=1;i<=n;++i)
{
    j=2;
    while(j<=n)
    {
        j=j*j;
        c=c+1;
    }
}

1. $O(nlog n)$
2. $O(n^{2})$
3. $O(nloglog n)$
4. $O(n)$

Answer 1

First consider how many times the inner loop runs.This can be found as :

       2^{2^k}   =  n   [As j begins from 2 and ends at n in inner loop and each time j = j²]

==>  2^k    =  log₂n

==>  k      = log(logn)

So inner loop runs log(logn) times..

And i runs n times independent of j..And for each i , j runs log(logn) times..

Hence overall complexity  =  O(nloglogn)

Hence 3) is the correct answer..

Comments

SIR, Can u pls explain this part a little bit ? 
 2^{2^k}   =  n   [As j begins from 2 and ends at n in inner loop and each time j = j²]

How did you get this 

---

Actually see

Initial value of j = 2

In next iteration j = j * j = 2²  =  4

In next iteration j = j * j = 4²  =  16  = 2^{2^2}

In next iteration j = 16 * 16  = 2^{2^3}

So in kth iteration j = 2^{2^k}

So ultimately j becomes n right..So equating 2^{2^k}  and n we get the value of k..