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).