Need help in understanding the answer of the Big-O complexity for this code

Admin 1
Viewed 96

According to the answer key, the answer is O(N). I didn't have enough time to see it carefully. I thought it was i++ and not i/=2 in the first loop so I wrote O(N^2). But now I am not sure what is the correct. I think it should be O(log n * log n).

Code:

int count = 0;
for (int i = N; i > 0; i /=2)
    for (int j = 0; j < i; j++)
        count++;

Image:

enter image description here

time-complexity c
1 Answers
  • At the first iteration of the outer loop, the inner loop is performed N times
  • At the second iteration, the inner loop is performed N/2 times
  • At each subsequent iteration, the inner loop is performed half as many times as in the previous iteration

The total number of iterations is equal to N + N/2 + N/4 + ... + 1, which is approximately equal to 2N.

Therefore, the total number of iterations is O(N)

user_16798490
Related