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 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)$.
