Let X be the random variable on the set of permutations of a set of n distinct integers {a 1 , a 2 , . . . , a n } 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.

Question

Answer the following part:
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 I j,k be the random variable with  _j,k (P ) = 1 if a_k precedes a _j  in P and I _j,k = 0 otherwise. Show that

f ) Show that
g) Show that E(I j,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 .