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

Related questions

0 votes
1 answer
2
asked Jan 7, 2017 in Algorithms by firki lama Junior (873 points) | 89 views
+1 vote
0 answers
3


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

34,774 questions
41,739 answers
118,909 comments
41,386 users