Find the time complexity of a given function

Question

For this program, it will be temporary complexity.

int count = 0;

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

In my opinion, this should be O(nlogn)because the cycle iis divided and at rest, and therefore the O(logn)cycle j O(n).

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

Answer 1

This is O(n):

The outer loop has O(logn)iterations, since it istarts with nand decreases by half by each iteration.

Now consider the number of iterations of the inner loop:

• In the first iteration of the outer loop, the inner loop has niterations (starting at i==n).

• n/2 ( i==n/2).

• ...

• log(n)'th ( ) 1 ( i==1).

, :

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