title: Complexity of a double for loop
body: <p>I am trying to figure out the complexity of a for loop using Big O notation. I have done this before in my other classes, but this one is more rigorous than the others because it is on the actual algorithm.  The code is as follows: </p>
  
  <pre><code>for(cnt = 0, i=1; i&lt;=n; i++) //for any size n
  {
      for(j = 1; j &lt;= i; j++)
      {
         cnt++;
      }
  }
  </code></pre>
  
  <p>AND</p>
  
  <pre><code>for(cnt = 0, i=1; i&lt;=n; i*=2) //for any size n
  {
      for(j = 1; j &lt;= i; j++)
      {
         cnt++;
      }
  }
  </code></pre>
  
  <p>I have arrived that the first loop is of O(n) complexity because it is going through the list n times. As for the second loop I am a little lost. I believe that it is going through the loop i times for each n that is tested. I have (incorrectly) assumed that this means that the loop is O(n*i) for each time it is evaluated. Is there anything that I'm missing in my assumption. I know that cnt++ is constant time. </p>
  
  <p>Thank you for the help in the analysis. Each loop is in its own space, they are not together. </p>