(15pts) We learned in class that the general quick sort algorithm selects a pivoting element x in A[1 to n], recursively sort an array consisting of all at most x excluding x itself, and that consisting of all greater thanx 3. Assume that A[1 to n] contains n distinct elements where n is divided by 100. Answer the questions (a) Your quick sort algorithm chooses any element in A as the pivoting element x with the equal probability. What is the probability that (s 100 th smallest in A) v (x ? th smallest in A) ? 99 n (b) Do the same trials as (a) for 5 times each independently to obtain five integers x1, x2, x3, x4,x,5 in A[1 to n]; because of the independence, some two might be the same. What is the probability 99 n that exactly three xi satisfy (Xi S 1 that (s 00 th smallest in A) (x s in th smallest in A) v (x > th smallest in A) V i > 00 th smallest in A)? (c) Do the same trial as (b), and let x be the median of the obtained five. What is the probability (d) With the same x, what is the probability that th smallest in A) ? 99 n 100 100 (e) Now your quick sort algorithm chooses x obtained by (C) as the pivoting element. Let p be the answer to (C), and q be the time required to select random five elements and find their median. Here's a simple running time recurrence with p and q: let T(n) be the average running time of the algorithm for n elements As the number of trials increases from 5 to 7, 9, , ?clgn 1 for some sufficiently large constant c>0, the probability p_(e.5)much. More detailed analysis shows this may speed-up the quick sort algorithm Fill in the blanks (e.1)-(e.5) to complete the description