CODEWITHSUNDEEP
c++time-complexity
Vanshika
Vanshika

Reputation: 59

Can anyone suggest time complexity of the following code

According to me the time complexity should be O(nlogn) as the outer loop works until n/2^k =1 and inner loop works for n times. Can anyone tell if i'm correct or not.

 while(n){ 
  j=n; 
  while(j>1){ 
    j-=1; 
  } 
  n/=2; 
}

Upvotes: 2

Views: 93

Answers (1)

fas
fas

Reputation: 1413

Inner cycle does n iterations, outer each iteration divides n by 2, so there are n + n/2 + n/4 + ... = 2n total iterations of the inner cycle and time complexity is O(n), not O(n log n).

Upvotes: 8

Related Questions