title: Big O analysis for this for loop
body: <pre><code> sum = 0;
   for (i = 1; i &lt;= n; i++) {    //#1
     for (j = 1; j &lt;= i * i; j++) {     //#2
        if (j % i == 0) {    //#3 
            for (k = 1; k &lt;= j; k++) {   //#4
               sum++;
           }
       }
    } 
  </code></pre>
  
  <p>}</p>
  
  <p>The above got me confusing </p>
  
  <pre><code>Suppose #1 runs for N times
      #2 runs for N^2 times
      #3 runs for  N/c since for N inputs N/c could be true conditions
      #4 runs for  N times
  </code></pre>
  
  <p>Therefore roughly I could be looking at O(N^5) . I am not sure. Please help clarify. </p>
  
  <p><strong>EDIT</strong> I was wondering the runtime at the <code>if(j%i==0)</code>. Since it takes <code>N^2</code> inputs from its parent loop it could be doing <code>(N^2)/c</code> executions instead of <code>N/c</code></p>