In this exercise we derive an estimate of the average-case complexity of the variant of the bubble sort algorithm that terminates once a pass has been made with no interchanges. Let X be the random variable on the set of permutations of a set of n distinct integers {a1, a2, . . . , an} with a1 < a2 < · · · < an such that X(P) equals the number of comparisons used by the bubble sort to put these integers into increasing order.
a) Show that, under the assumption that the input is equally likely to be any of the n! permutations of these integers, the average number of comparisons used by the bubble sort equals E(X).
b) Use Example 5 in Section 3.3 to show that E(X) ≤ n(n − 1)/2.
c) Show that the sort makes at least one comparison for every inversion of two integers in the input.
d) Let I (P) be the random variable that equals the number of inversions in the permutation P. Show that E(X) ≥ E(I).
e) Let Ij,k be the random variable with Ij,k(P ) = 1 if ak precedes aj in P and Ij,k = 0 otherwise. Show that I (P) = Σk Σ jf) Show that E(I ) = Σk Σkjg) Show that E(Ij,k) = 1/2.
h) Use parts (f) and (g) to show that E(I) =n(n − 1)/4.
i) Conclude from parts (b), (d), and (h) that the average number of comparisons used to sort n integers is Ɵ(n2).