@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

The Gateway to Computer Science Excellence

+1 vote

+4 votes

Best answer

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

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

0

@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

52,345 questions

60,472 answers

201,800 comments

95,278 users