The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
261 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
      }
    }
}
asked in Programming by (241 points) | 261 views

1 Answer

+3 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)$$
answered by Veteran (385k points)
selected by
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,932 questions
52,335 answers
182,384 comments
67,817 users