Calculation of the complexity of an algorithm with 3 cycles

Question

I tried to solve the following exercise:

What is the worst-case growth order of the next 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 complexity is O (n ⁴ ), however the correct answer is:

Answer: N ⁷

For a given value i, the body of the inner loop itself is executed 1 ² + 2 ² + 3 ² + ... + (i ² ) ² ~ 1/3 i ⁶ times. Summation over all values ​​of i gives ~ 1/21 N ⁷ .

I would like to help understand this answer and the correct way to calculate complexity in this case.

EDIT: In particular, I do not understand this statement:

1 ² + 2 ² + 3 ² +... + (i ²) ² ~ 1/3 ⁶

² + 2 ² + 3 ² +... + (i ²) ² ~ ⁴

Answer 1

EDIT:

, . i :

for (int j = 1; j <= i*i; j++)
    for (int k = 1; k <= j*j; k++)
        sum++;

j-loop? - 2 . k- j ^ 2 , , j 1 ^ 2.

j = 1, k- 1 ^ 2 . j = 2, k-loop 2 ^ 2 . j = 3, 3 ^ 2 . k- j, 1 ^ 2 + 2 ^ 2 + 3 ^ 2 +... + (i ^ 2) ^ 2, j 1 ^ 2. , , :

1 ² + 2 ² + 3 ² +... + (i ²) ² ~ 1/3 ⁶ times.

---

. j^2 () j, i^2 i, N . :

, , 7- N, , O (N ^ 7).

, sum, :

var sum = 0;
var N = 10;

for (var i = 1; i <= N; i++)
    for (var j = 1; j <= i*i; j++)
        for (var k = 1; k <= j*j; k++)
            sum++;

function T(N) { return (1/420)*N*(1+N)*(1+2*N)*(8+11*N+21*N*N+20*N*N*N+10*N*N*N*N); }

console.log(sum===T(N));

: http://jsfiddle.net/wby9deax/. , N, , ( : N, , , , ).

Answer 2

int sum = 0;
for (int i = 1; i <= N; i++)            -- O(N^1)
    for (int j = 1; j <= i*i; j++)      -- O(N^2)
        for (int k = 1; k <= j*j; k++)  -- O(N^4)
            sum++;

( ), O (N ¹ & times; N ² & times; N ⁴) = O (N ^{1 + 2 + 4}) = O (N ⁷)

---

EDIT: , :

1 ² + 2 ² + 3 ² +... + (i ²) ² ~ 1/3 ⁶

, N , "& hellip;" .

Answer 3

because there will be N ^ 1 loops - first for N ^ 2 loops - second for N ^ 4 loops - third for and N ^ 1 * N ^ 2 * N ^ 4 = N ^ 7

Answer 4

I think it’s nice to replace the variables (i, j and k) with N values.

for (int i = 1; i <= N; i++) //<- i = N
    for (int j = 1; j <= i*i; j++) //<- i*i = N*N
        for (int k = 1; k <= j*j; k++) //<- j*j = (i*i)*(i*i) =  N*N*N*N

In the first loop, the number of iterations will be N, this simple part. In the second loop, the number of iterations will be N*N. In the third - N*N*N*N.

So, the number of iterations will be equal to N (first cycle), times N*N(second), times N*N*N*N(third), therefore N*(N*N)*(N*N*N*N)=N^7