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;
}
Can anyone suggest time complexity of the following code
Viewed 77
1 Answers
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).
Related