# Homework Help: Complexity of nested for-loops

1. Oct 6, 2009

### Thomas_

1. The problem statement, all variables and given/known data
Find the statement count (not the worst-case scenario) of the following for-loop.

Code (Text):
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];
}
}

3. 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?