+1 vote
211 views

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

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