Why is time complexity of `fun` $O(n)$?

Question

Why is time complexity of fun $O(n)$?

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 think because of the nested loop it should be $O(n^2)$.

Answer 1

The inner (count += 1) operation is executed approximately $$n+\frac{n}{2}+\frac{n}{4}+\cdots=n\left(1+\frac{1}{2}+\frac{1}{4}+\cdots\right)=2n$$ times.

Answer 2

The outer loop isn't looping through all linear values from n to 0. It is halving each time. So it goes: $n, \frac{n}{2}, \frac{n}{4}, \frac{n}{8}, \frac{n}{16}, ...$ The inner loop is called this many times so you need to work out $n+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\frac{n}{16}+... = 2n$. Hence its $O(n)$.