title: Big-O analysis of for loop algorithm
body: <p>I'm having trouble analyzing the following for loop algorithm:</p>
  
  <pre><code>for (int i = 1; i &lt; n; i = i * C)
      for (int j = 0; j &lt; i; j++)
          Sum[i] += j * Sum[i];
  </code></pre>
  
  <p>I know that the first line has a complexity of O(logn) (as long as C > 1), but what has me stumped is the second line. I believe I understand the basics of what is happening with it:  </p>
  
  <p>For example, </p>
  
  <blockquote>
    <p>if n=20, the inner loop will do 1+2+4+8+16 "work".  </p>
  </blockquote>
  
  <p>But I don't know how to write that out. I'm nearly sure the total work done altogether in the loops is O(n), and that the first line is O(logn), but how do I more concretely specify what the middle line does?</p>