Question

What is the time complexity?

main()
{
    n=2^2^k, k>0
    for(i = 1 to n)
    {
      j=2
      while(j ≤ n)
      {
        j=j^2
      }
    }
}

Answer 1

I assume 2^2^k is evaluated as 2^(2^k)
In each iteration of while loop j is becomeing 2^2^l (where l is the loop iteration count) and loop terminates when j = 2^2^k. So, l must be equal to k when loop terminates. So, complexity of while loop is $\Theta(k)$. Now, the outher for loop runs for $n$ iterations and hence the complexity of the entire code is
$$\Theta(nk)\\
=\Theta(n\log \log n)$$

Comments

@Arjun Sir I think the complexity of inner while loop is 2^k..

and since outer loop is running n times so , the time complexity must be n*2^k..

which is nlogn