What is the complexity of this sum algorithm?
algorithm, c
Solution
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)`.
Problem
``` #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?