What is the complexity of this sum algorithm?

Question

#include <stdio.h>

int main() {
    int N = 8;  /* for example */
    int sum = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= i*i; j++)
            sum++;

    printf("Sum = %d\n", sum);
    return 0;
}

for each n value (i variable), j values will be n^2. So the complexity will be n . n^2 = n^3. Is that correct?

If problem becomes:

#include <stdio.h>

int main() {
    int N = 8;  /* for example */
    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++;

    printf("Sum = %d\n", sum);
    return 0;
}

Then you use existing n^3 . n^2 = n^5 ? Is that correct?

Answer 1

We have i and j < i*i and k < j*j which is x^1 * x^2 * (x^2)^2 = x^3 * x^4 = x^7 by my count.

In particular, since 1 < i < N we have O(N) for the i loop. Since 1 < j <= i^2 <= N^2 we have O(n^2) for the second loop. Extending the logic, we have 1 < k <= j^2 <= (i^2)^2 <= N^4 for the third loop.

Inner to Outer loops, we execute up to N^4 times for each j loop, and up to N^2 times for each i loop, and up to N times over the i loop, making the total be of order N^4 * N^2 * N = N^7 = O(N^7).

Answer 2

I think the complexity is actually O(n^7).

The first loop executes N steps. The second loop executes N^2 steps.

In the third loop, j*j can reach N^4, so it has O(N^4) complexity.

Overall, N * N^2 * N^4 = O(N^7)

Answer 3

For i = 1 inner loop runs 1^1 times, for i = 2inner loop runs 2^2 times .... and for i = N inner loop runs N^N times. Its complexity is (1^1 + 2^2 + 3^3 + ...... + N^N) of order O(N^3).

In second case, for i = N first inner loop iterates N^N times and hence the second inner loop(inner most) will iterate up to N * (N^N) * (N^N) times. Hence the complexity is of order N * N^2 * N^4, i.e, O(N^7).

Answer 4

Yes. In the first example, the i loop runs N times, and the inner j loop tuns i*i times, which is O(N^2). So the whole thing is O(N^3).

In the second example there is an additional O(N^4) loop (loop to j*j), so it is O(N^5) overall.

For a more formal proof, work out how many times sum++ is executed in terms of N, and look at the highest polynomial order of N. In the first example it will be a(N^3)+b(N^2)+c(N)+d (for some values of a, b, c and d), so the answer is 3.

NB: Edited re example 2 to say it's O(N^4): misread i*i for j*j.

Answer 5

Consider the number of times all loops will be called.

int main() {
int N = 8;  /* for example */
int sum = 0;
for (int i = 1; i <= N; i++)   /* Called N times */
    for (int j = 1; j <= i*i; j++) /* Called N*N times for i=0..N times */
        for (int k = 1; k <= j*j; k++) /* Called N^2*N^2 times for j=0..N^2 times and i=0..N times */ 
            sum++;

printf("Sum = %d\n", sum);
return 0;
}

Thus sum++ statement is called O(N^4)*O(N^2)*O(N) times = O(N^7) and this the overall complexity of the program.

Answer 6

The incorrect way to solve this (although common, and often gives the correct answer) is to approximate the average number of iterations of an inner loop with its worst-case. Here, the inner loop loops at worst O(N^4), the middle loop loops at worst O(N^2) times and the outer loop loops O(N) times, giving the (by chance correct) solution of O(N^7) by multiplying these together.

The right way is to work from the inside out, being careful to be explicit about what's being approximated.

The total number of iterations, T, of the increment instruction is the same as your code. Just writing it out:

T = sum(i=1..N)sum(j=1..i^2)sum(k=1..j^2)1.

The innermost sum is just j^2, giving:

T = sum(i=1..N)sum(j=1..i^2)j^2

The sum indexed by j is a sum of squares of consecutive integers. We can calculate that exactly: sum(j=1..n)j^2 is n*(n+1)*(2n+1)/6. Setting n=i^2, we get

T = sum(i=1..N)i^2*(i^2+1)*(2i^2+1)/6

We could continue to compute the exact answer, by using the formula for sums of 6th, 4th and 2nd powers of consecutive integers, but it's a pain, and for complexity we only care about the highest power of i. So we can approximate.

T = sum(i=1..N)(i^6/3 + o(i^5))

We can now use that sum(i=1..N)i^p = Theta(N^{p+1}) to get the final result:

T = Theta(N^7)