Stanko - 1 year ago 158
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      |
``````

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