Time complexity of fun()?

Question

I was going through this question to calculate time complexity.

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;
}

My first impression was O(n log n) but the answer is O(n). Please help me understand why it is O(n).

Answer 1

The inner loop does n iterations, then n/2, then n/4, etc. So the total number of inner loop iterations is:

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

(See Geometric series), and therefore is O(n).