title: Time complexity for nested loops?
body: <p>a)</p>
  
  <pre><code>sum = 0;
  for(i=1;i&lt;2*n;i++)
   for(j=1;j&lt;i*i;j++)
    for(k=1;k&lt;j;k++)
     if (j % i == 1)
     sum++;
  </code></pre>
  
  <p>b)</p>
  
  <pre><code>sum = 0;
  for(i=1;i&lt;2*n;i++)
   for(j=1;j&lt;i*i;j++)
    for(k=1;k&lt;j;k++)
     if (j % i)
     sum++;
  </code></pre>
  
  <p>I chanced the above two pseudo code above while looking for algorithm analysis questions to practice on. The answers for the above two snippets are O(n<sup>4</sup>) and O(n<sup>5</sup>) respectively.</p>
  
  <p>Note that the running time corresponds here to the number of times the operation
  sum++ is executed.</p>
  
  <p>How is it that the time complexity for the above two algorithms different by an order of <code>n</code> when the only difference is the <code>if</code> loop testing for equality to <code>1</code>? How would I go about counting the O(n) complexity for such a question?</p>