1. Question 1: The Random Quicksort algorithm works as follows. We assume that the numbers are pairwise different. (a) If the array has one element or is empty return the array (b) Otherwise choose a number at random from A1], A2],.. ,An]. This number is called a pivot. Let r be the value of the chosen entry (c) Create an array As of all elements smaller than x, and AL the elements that are larger than x (d) Recursively sort As and AL and return As, x, AL. Let B[1], B2],... , B[n| be the array A sorted, namely B[i] is the ith smallest number in A. Let Xj be the random variable that has value of 1 if B[i] and B j) are compared, and has value 0 otherwise. Let T' be the number of comparisons in Random Quicksort (a) Show that T--CpX, (b) Show that if B[p] for p j is chosen as pivot this does not change the probability that B[i] and Blj] will be compared (c) Show that if the first element chosen as pivot among B[i, Bfi+1],... , Blj] is Alp for i ,2/(j-i + 1) (f) Show that for i-1, >i P(B[1] and Blil are compared) 2(1+ 1/2+ 1/2+ (g) Show that E(T) 3 2 -n Inn +O(n)