Let x_1, . . . , x_n be a list of n distinct numbers. We say that ai and aj are inverted if i aj. The Bubblesort sorting algorithm swaps pairwise adjacent inverted numbers in the list until there are no more inversions (hence the list is sorted).

Assuming that the input to Bubblesort is a uniformly at random selected permutation of the set {x_1,...,x_n}, compute the expected number of inversions that need to be corrected by Bubblesort.

Let ri,, Tn be a list of n distinct numbers. We say that ai and a, are inve rted if i aj. The Bubblesort sorting algorithm swaps pairwise adjacent inverted numbers in the list until there are no more inversions (hence the list is sorted). Assuming that the input to Bubblesort is a uniformly at random selected permutation of the set {x?,..., Tn), compute the expected number of inversions that need to be corrected by Bubblesort