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.

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.

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 <= ii; j++) for (int k = 1; k <= jj; 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.

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.