Find the time complexity of a given function

Question

For the given program what will be the time complexity.

int count = 0;

    for(int i = n; i > 0; i /= 2)
    {
        for(int j = 0; j < i; j++)
        {
            count++;
        }
    }

To my understanding, it should be O(nlogn) because the i loop is divide and conquer and hence O(logn) and the j loop is O(n).

However, the correct answer is O(n). Can someone explain why?

Eran · Accepted Answer

It's O(n):

The outer loop has O(logn) iterations, since i starts at n and gets halved on each iteration.

Now let's consider the number of iterations of the inner loop:

In the first iteration of the outer loop, the inner loop has n iterations (since i==n).
In the second iteration of the outer loop, the inner loop has n/2 iterations (since i==n/2).
...
In the log(n)'th (and final) iteration of the outer loop, the inner loop has 1 iteration (since i==1).

Summing all the inner loop iterations we get:

n + n/2 + n/4 + ... + 1 <= 2*n = O(n)

Donate For Us