Question

Show that the worst-case and average-case time complexities for the number of assignments of records performed by the Exchange Sort algorithm (Algorithm 1.3) are given by

          W(n) = 3n(n-1)/2 ≈ n²/2 and A(n) = 3n(n-1)/4 ≈ n²/4

Answer 1

Let us define what is a worst-case and average-case scenario for a sorting algorithm, Worst case is defined as an array which is reversely sorted. The average case is, in general, between the worst case and best case i.e takes at least half the time of the worst-case scenario.

An exchange sort algorithm compares each element with all other elements starting from the first element and swaps if the latter element is lesser than the former. So for a worst-case scenario, the first element is compared with n-1 elements, the second element is compared with n-2 elements and so on. The second last element is compared just with the last element.

Hence number of comparisons = (n-1) + (n-2) + (n-3)......+(n-(n-1)) + (n-n)

There are n terms in the above equation. This can be simplifies as:

Number of comparisons = n*n + (1+2+3+....n)

Second term is arithmetic series 1+2+3.... +n= n(n+1)/2 = (n^2 +n)/2

Therefore, number of comparisons = n^2 + (n^2 + n)/2 = (3n^2 +n)/2 = (3n^2 -3n +2n)/2 = 3n(n-1)/2 + n

Hence worst case time complexity = 3n(n-1)/2 ~ n^2/2

Average case complexity takes around half the time as worst case complexity i.e 3n(n-1)/4 ~ n^2/4