title: Running time complexity of a code fragment
body: <p>Here is the fragment:</p>
  
  <pre><code>sum1=0;
      for(i=1;i&lt;=n;i++)
        for(j=1;j&lt;=n;j++)
          sum1++
  sum2=0
      for(k=1;k&lt;=n;k*=2)
        for(j=1;j&lt;=k;j++)
          sum2++   
  </code></pre>
  
  <p>Below is the answer: </p>
  
  <p>2 assignment statements – O(1) each
  1st nested loop – O(n2)
  2nd nested loop – O(n)
  Running time complexity of code fragment = O(1) + O(n^2) + O(1) + O(n) = O(n2)</p>
  
  <p>But here is how I worked it out:</p>
  
  <p>2 assignments:- O(1).
  First nested loop: O(n*n)=O(n^2)
      Second nested loop: </p>
  
  <p>Outer loop runs n times..
  Now the inner loop will be executed (1+2+3+.....+(n-1)+n) times
  which gives n(n+1)/2 =O(n^2)</p>
  
  <p>Total running time = O(n^2)+O(n^2)+O(1)=O(n^2)</p>
  
  <p>And yes I've done some research and I came across the following:</p>
  
  <p>In a loop if an index jumps by an increasing amount in each iteration the sequence has complexity log n.</p>
  
  <p>In that case I suppose the second loop will have complexity (n-1)/2*logn...which will be equal to O(n*log n).</p>
  
  <p>I'm really confused with the second loop whether it should be O(n)..O(n^2) or O(nlogn)..</p>
  
  <p>HELP PLEASE</p>