TIME COMPLEXITY

Question

i=n;

while(i>0)

{

j=1;

while(j<=n)

{

j=2*j;

}

i=i/2;

}

Comments

Is it loglogn?

---

@Mayankprakash

it is (log n) * (log n) but not log(log n)

why?

outer loop executes log n times

inner loop executes log n times for every outer loop ===> (log n) * ( log n)

it is asymptotically equivalent to

for( i=n; i>0 ; i=i/2 )

{

   for ( j=1,j ≤ n; j=j*2)

   {

   }

}

Moreover, if you not giving explanation, add it as comment, not as answer.

Answer 1

The first while loop runs O(logn) times. for each outer loop inner runs O(logn) times.So.the time complexity is O(logn)*O(logn)=O((logn)^2)