title: Understand algorithm complexity
body: <p>Can somebody explain why complexity of the algorithm bellow is O(log N)?
  This is one of the questions from <a href="https://www.interviewbit.com" rel="nofollow">https://www.interviewbit.com</a> and their explanation/tip is not clear to me (see bellow the code block).</p>
  
  <pre><code>    int a = 0, i = N;
      while (i &gt; 0) {
          a += i;
          i /= 2;
      }
  </code></pre>
  
  <p><code>1. Notice that in every iteration, i goes to i / 2</code>  &lt;--- got that</p>
  
  <p><code>2. So, after x iterations, i will be N / 2^x</code> &lt;--- I agree, but how did I suppose to figure that out (it doesn't come to me just from the thin air).</p>
  
  <p><code>3. We have to find first x such that N / 2^x &lt; 1 OR 2^x &gt; N</code> &lt;-- understand it from the previous step. And also understand that is solution from this step is <code>x = log N</code>.</p>
  
  <p>So, entire questions for me is why is it i=N/2^x after x iterations?</p>