Complexity of an algorithm I tried to solve the following exercise :
What is the order of growth of the worst case running time of the following code fragment
as a function of N?
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++;

and I found that the complexity is O(n^4), however the correct answer is  :

The answer is : N^7
For a given value of i, the body of the innermost loop is executed 1^2 + 2^2 + 3^2 + ... + (i^2)^2 ~ 1/3 i^6 times. Summing up over all values of i yields ~ 1/21 N^7.

I would like some help to understand this answer and the correct way to calculate complexity in this case.
It will be easier to analyze things if we break them down into several different procedures:

int I(int n) { for (i = 1; i &lt;= n; i++) J(i); }
int J(int n) { for (j = 1; j &lt;= n*n; j++) K(j); }
int K(int n) { for (k = 1; k &lt;= n*n; k++) sum++; }


Instead of measuring time complexity, let us use instead the number of times sum is incremented as our complexity measure. Also, let $I(n),J(n),K(n)$ double as the complexity of the functions with matching name.

It is not hard to see that $K(n) = n^2$. Therefore
$$
J(n) = \sum_{j=1}^{n^2} K(j) = \sum_{j=1}^{n^2} j^2.
$$
Now we invoke the formula $\sum_{j=1}^m j^2 \sim m^3/3$. Substituting $m = n^2$, we get
$$
J(n) \sim \frac{n^6}{3}.
$$
Continuing,
$$
I(n) = \sum_{i=1}^n J(i) \sim \frac{1}{3} \sum_{i=1}^n i^6 \sim \frac{1}{21} n^7.
$$
Some of these estimates are not completely rigorous, but you can make them rigorous with a bit of work.