Time complexity fun ()?

Question

I considered this question to calculate the complexity of time.

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 this is O (n).

Answer 1

The inner loop performs n iterations, then n/2 , then n/4 , etc. Thus, the total number of iterations of the inner loop:

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

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