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 <= N; i++) for (int j = 1; j <= i*i; j++) for (int k = 1; k <= 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.