Stanko Stanko - 6 days ago 6
Java Question

Complexity in tilde notation of nested for loops

How do I find the complexity in tilde notation of the following algorithm:

for (int j = 0; j < N; j++) {

for (int k = j + 1; k < N; k++) {

array[k] = array[j];

}

array[j] = k
}


I've made a table with how many times the inner for-loop loops if
N = 9
:

| j | # of loops |
|:-----------|------------:|
| 0 | 8 |
| 1 | 7 |
| 2 | 6 |
| 3 | 5 |
| 4 | 4 |
| 5 | 3 |
| 6 | 2 |
| 7 | 1 |
| 8 | 0 |

Answer

As you evaluate, the number of inner iterations decreases linearly from 8 down to 0, i.e. it is 4 on average, for a total of 4.9=36.

More generally, the average is (N-1)/2 and the total N.(N-1)/2.

Consequently, I(N) ~ N²/2, in terms of the iteration count.

In terms of memory accesses (R+W), it's the double: A(N) ~ N². (The extra access in the outer loop adds a negligible N contribution.)

Comments