title: Big O Notation Homework--Code Fragment Algorithm Analysis?
body: <p>For homework, I was given the following 8 code fragments to analyze and give a Big-Oh notation for the running time.  Can anybody please tell me if I'm on the right track?  </p>
  
  <pre><code>//Fragment 1
  for(int i = 0; i &lt; n; i++)
      sum++;
  </code></pre>
  
  <p>I'm thinking O(N) for fragment 1</p>
  
  <pre><code>//Fragment 2
  for(int i = 0; i &lt; n; i+=2)
      sum++;
  </code></pre>
  
  <p>O(N) for fragment 2 as well</p>
  
  <pre><code>//Fragment 3
  for(int i = 0; i &lt; n; i++)
      for( int j = 0; j &lt; n; j++)
          sum++;
  </code></pre>
  
  <p>O(N^2) for fragment 3</p>
  
  <pre><code>//Fragment 4
  for(int i = 0; i &lt; n; i+=2)
      sum++;
  for(int j = 0; j &lt; n; j++)
      sum++;
  </code></pre>
  
  <p>O(N) for fragment 4</p>
  
  <pre><code>//Fragment 5
  for(int i = 0; i &lt; n; i++)
      for( int j = 0; j &lt; n * n; j++)
          sum++;
  </code></pre>
  
  <p>O(N^2) for fragment 5 but the n * n is throwing me off a bit so I'm not quite sure</p>
  
  <pre><code>//Fragment 6
  for(int i = 0; i &lt; n; i++)
      for( int j = 0; j &lt; i; j++)
          sum++;
  </code></pre>
  
  <p>O(N^2) for fragment 6 as well</p>
  
  <pre><code>//Fragment 7
  for(int i = 0; i &lt; n; i++)
      for( int j = 0; j &lt; n * n; j++)
          for(int k = 0; k &lt; j; k++)
              sum++;
  </code></pre>
  
  <p>O(N^3) for fragment 7 but once again the n * n is throwing me off</p>
  
  <pre><code>//Fragment 8
  for(int i = 1; i &lt; n; i = i * 2)
      sum++;
  </code></pre>
  
  <p>O(N) for fragment 8</p>