title: Calculating the complexity of an algorithm with 3 loops
body: <p>I tried to solve the following exercise :</p>
  <p>What is the order of growth of the worst case running time of the following code fragment
  as a function of N?</p>
  <pre><code>int sum = 0;
  for (int i = 1; i &lt;= N; i++)
      for (int j = 1; j &lt;= i*i; j++)
          for (int k = 1; k &lt;= j*j; k++)
              sum++;
  </code></pre>
  <p>and I found that the complexity is O(n<sup>4</sup>), however the correct answer is  :</p>
  <blockquote>
  <p>The answer is : N<sup>7</sup></p>
  <p>For a given value of i, the body of the innermost loop is executed 1<sup>2</sup> + 2<sup>2</sup> + 3<sup>2</sup> + ... + (i<sup>2</sup>)<sup>2</sup> ~ 1/3 i<sup>6</sup> times. Summing up over all values of i yields ~ 1/21 N<sup>7</sup>.</p>
  </blockquote>
  <p>I would like some help to understand this answer and the correct way to calculate complexity in this case.</p>
  <p>EDIT : In particular, I don't understand this statement :</p>
  <p>1<sup>2</sup> + 2<sup>2</sup> + 3<sup>2</sup> + ... + (i<sup>2</sup>)<sup>2</sup> ~ 1/3 i<sup>6</sup></p>
  <p>Because for me, <sup>2</sup> + 2<sup>2</sup> + 3<sup>2</sup> + ... + (i<sup>2</sup>)<sup>2</sup> ~ i<sup>4</sup></p>