Algorithm Time Complexity: i/=2 in loops

Viewed 17049
int fun(int n) {
    int count = 0;
    for (int i = n; i > 0; i /= 2)
        for (int j = 0; j < i; j++)
            count += 1;
    return count;
}

I'm a very new to the time complexities calculations. For this algorithm, I get the answer to be O(nlogn), but the answer is apparently O(n).

My logic was the outer loop has an exponential decline and will occur log_base2_(N) times. The inner loop will run a total of N times as it becomes a geometric sum (first iteration it is N/2 times, then N/4, then N/8 ...). If I put these together and multiply them as a result of the nested loop, that's where I'm coming up with O(NlogN). Am I missing something obvious?

1 Answers
Related