title: Running time of for loop
body: <p>I seem to understand the basic concepts of easier loops like so...the first loop runs in O(n), as does the inner loop. Because they're both nested, you multiply to get a total running time of O(n^2).</p>
  
  <pre><code>sum = 0; 
  for ( i = 0; i &lt; n; i++ ) 
    for j = 0; j &lt; n; j++ ) 
      ++sum; 
  </code></pre>
  
  <p>Though when things start getting switched around, I get completely lost as to how to figure it out. Could someone explain to me how to figure out running time for both of the following? Also, any links to easy to understand references that could further help me improve is also appreciated.  Thanks!</p>
  
  <pre><code>sum = 0; 
  for( i = 0; i &lt; n; i += 2 ) 
    for( j = 0; j &lt; n; j++ ) 
      ++sum; 
  </code></pre>
  
  <p>The only thing I can gather from this is that the inner loop runs in O(n). The i+=2 really throws me off in the outer loop.</p>
  
  <pre><code>sum = 0; 
  for( i = 1; i &lt; n; i *= 2 ) 
    for( j = 0; j &lt; n; j++ ) 
      ++sum; 
  </code></pre>
  
  <p>From my attempt...outer loop is O(log(n)), inner is O(n), so total is O(n log(n))?</p>