Complexity of nested for-loops

[Thomas_]

Homework Statement

Find the statement count (not the worst-case scenario) of the following for-loop.

for (int k = 0; k < N; k += 1) {
        for (int m = 0; m < k; m += 1) {
            sum = sum + values[k][m];
        }
        for (int p = k; p < N; p += 1) {
            sum = sum + values[k][m];
        }
    }

The Attempt at a Solution

For the outer loop:
k < N and k += 1 are both executed N-times => +2N
int k=0 and k<N are both executed once more at the beginning => +2
both inner loops are executed N times => +n(inner-loop-count)

For the first inner loop:
Similar to the outer loop, except that it has no inner loop and everything is multiplied by N because of the outer loop => n(2N + N + 2) => 3N^2 + 2n

For the second outer loop:
It is executed one time less for each time N increases, but I cannot figure out a formula for it.
For N=1 -> 3n+2 =5
for N=2 -> 3n+2 +3(n-1) + 2 = 13
for N=3 -> 3n+2 +3(n-1) + 2 + 3(n-2) + 2 = 24
...

But what is the general formula?

 

[KataKoniK]

The statement count for the second inner loop would be similar to the first inner loop, except that the loop condition is different (p < N instead of m < k) and the indices used for the sum are different (values[k][p] instead of values[k][m]). So the statement count for the second inner loop would be: n(2N + N + 2) => 3N^2 + 2n

To find the statement count for the second outer loop, we can look at the pattern of the statement count for the first outer loop. For N=1, the statement count was 5. For N=2, the statement count was 13. For N=3, the statement count was 24. This pattern follows the formula: 3N^2 + 2n + 3 + 2 + 3 + ... + 3(N-1) + 2. This can be simplified to: 3N^2 + 2n + 3(N-1) + 2(N-1). Further simplifying, we get: 3N^2 + 5N - 5.

Therefore, the total statement count for the given for-loop would be:
2N + 2 + 3N^2 + 2n + 3N^2 + 2n + 3N^2 + 5N - 5
= 8N^2 + 9N + 4

In general, the statement count for this for-loop would have a time complexity of O(N^2).

 

[Mene]

The complexity of nested for-loops can be measured by the number of statements executed, also known as the statement count. In the given for-loop, the statement count can be calculated as follows:

- The outer loop is executed N times, with 2 statements executed each time (k < N and k += 1) => 2N statements
- The first inner loop is also executed N times, with 3 statements executed each time (m < k, m += 1, and sum = sum + values[k][m]) => 3N statements
- The second inner loop is executed N times, with 3 statements executed each time (p < N, p += 1, and sum = sum + values[k][m]) => 3N statements

Therefore, the total statement count for this for-loop is 2N + 3N + 3N = 8N. This means that the complexity of this nested for-loop is O(N), as the statement count increases linearly with the value of N. However, the exact number of statements executed may vary depending on the values of N and the specific statements within the loop.