The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
219 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) | 219 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 (355k points)
selected by

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

38,017 questions
45,509 answers
131,693 comments
48,732 users