Why is time complexity of `fun` $O(n)$? 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)$.

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.
