title: Time complexity of fun()?
body: <p>I was going through this question to calculate time complexity.</p>
  
  <pre><code>int fun(int n)
  {
    int count = 0;
    for (int i = n; i &gt; 0; i /= 2)
       for (int j = 0; j &lt; i; j++)
          count += 1;
    return count;
  }
  </code></pre>
  
  <p>My first impression was <em>O</em>(n log n) but the answer is <em>O</em>(n). Please help me understand why it is <em>O</em>(n).</p>