Stanko - 1 year ago 122

Java Question

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 Source

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