Let A[O .. n - 1] be an array of n sortable elements. (For simplicity, you can assume that all the elements are distinct.) A pair (A(i], A[j]) is called an inversion if i A[j]. a. What arrays of size...

Let A[O .. n - 1] be an array of n sortable elements. (For simplicity, you can assume that all the elements are distinct.) A pair (A(i], A[j]) is called an inversion if i <> A[j].

a. What arrays of size n have the largest number of inversions and what is this number? Answer the same questions for the smallest number of inversions.

b. Show that the average-case number of key comparisons in insertion sort is given by the formula