7-5 Median-of-3 partition One way to improve the RANDOMIZED-QUICKSORT procedure is to partition around a pivot that is chosen more carefully than by picking a random element from the subarray. One common approach is the median-of-3 method: choose the pivot as the median (middle element) of a set of 3 elements randomly selected from the subarray. (See Exercise 7.4-6.) For this problem, let us assume that the elements in the input array A[1n] are distinct and that n3. We denote the Problems for Chapter 7 189 sorted output array by A[1n]. Using the median-of-3 method to choose the pivot element x, define pi=Pr{x=A[i]}. a. Give an exact formula for pi as a function of n and i for i=2,3,,n1. (Note that p1=pn=0.) b. By what amount have we increased the likelihood of choosing the pivot as x=A[L(n+1)/2], the median of A[1n], compared with the ordinary implementation? Assume that n, and give the limiting ratio of these probabilities