title: Big O of Nested Loop (int j = 0; j < i; j++)
body: <pre><code>for (int i = n; i &gt; 0; i /= 2) {
     for (int j = 0; j &lt; i; j++) {
       //statement
     }
  }
  Answer: O(N)
  </code></pre>
  
  <p>I know that the first loop for <code>for (int i = n; i &gt; 0; i /= 2)</code> results in <code>O(log N)</code>.</p>
  
  <p>The second loop <code>for (int j = 0; j &lt; i; j++)</code> depends on <code>i</code> and will iterate first <code>i</code> times then <code>i / 2</code>, <code>i / 4</code>, ... times. (where <code>i</code> depends on <code>n</code>)</p>
  
  <p>I don't know the Big O for the second loop, but I thought the answer would be <code>O(log N * something)</code> where <code>O(log N)</code> is the outer loop and <code>something</code> is the inner loop? </p>
  
  <p>How do you get <code>O(N)</code>?</p>