(Median-of-3 Partition) One way to improve the RANDOMIZED-QUICKSORT is to choose the pivot for partitioning more carefully than by picking a random element from the array. One common approach is to choose the pivot as the median of a set of 3 elements randomly selected from the array. Assume that all elements in the array are distinct. Please answer following questions.

(a) What is the probability of getting an OK split if the pivot is chosen at random? Explain. (A split is OK if the smaller piece has at least n/4 elements.)

(b) Roughly, what is the probability of getting an OK split with the new median-of-3 method? Explain.

(c) Let I be the indicator random variable for getting an OK split using the median-of-3 partition:

1 if the split is OK

I =

0 otherwise

What is the expectation of I?