title: Determine Big-O runtime for these loops
body: <p>I am trying to determine the Big-O runtimes for these loops.  I believe the answers I have are correct, but I would like to check with the community.</p>
  
  <pre><code>int sum = 0;
  for (int i = 1; i &lt;= n*2; i++ )
     sum++;
  </code></pre>
  
  <p>My answer is O(n)</p>
  
  <p>This is because the loop iterates n x 2 times.  We drop the 2 and are left with n.  Therefore O(n).</p>
  
  <pre><code>int sum = 0;
  for ( int i = 1; i &lt;= n; i++)
     for ( int j = n; j &gt; 0; j /= 2)
        sum++;
  </code></pre>
  
  <p>My answer is O(n lgn)</p>
  
  <p>The outer loop iterates n times.  The inner loop iterates from n down to 0, but only through half of the items.  This works out to be Log base 2 of n.  We drop the 2 and keep log n.  The inner loop (log n) times the outer loop (n), gives us O(n lgn).</p>
  
  <pre><code>int sum = 0;
  for ( int i = 1; i &lt;= n; i++)
     for ( int j = i; j &lt;= n; j += 2)
        sum++;
  </code></pre>
  
  <p>My answer is O(n^2)</p>
  
  <p>This one is easy.  The inner loop and outer loop each iterate n times.  n x n = n^2.  Therefore O(n^2).</p>
  
  <pre><code>int sum = 0;
  for ( int i = 1; i &lt;= n * n; i++)
     for ( int j = 1; j &lt; i; j++ )
        sum++;
  </code></pre>
  
  <p>My answer is O(n^3)</p>
  
  <p>Are my answers correct?  If not, how can I correct them?</p>