Exercise 2.7. We are interested in finding the k th smallest element from a set A of n elements. In this exercise we assume that all elements in A are distinct. Below, we describe the procedure small (A,k) to find such an element. This procedure uses a sub-routine partition (B,q) that, given a set B of distinct elements and a pivot element qB, partitions the set B into a set S with all elements in B that are strictly smaller than q and a set L with all elements in B that are strictly larger than q. Note that SL{q}=B. The subroutine partition (B,q) can be implemented by scanning each element of B and deciding to put it into the set S or L. The running time of this subroutine is therefore O(B). Algorithm small (A,k) is described in Algorithm 2. \begin{tabular}{l} \hline Algorithm 2: Algorithm small (A,k). \\ \hline 1 Let qA; \\ 2 Let (S,L) be the partition obtained by partition (A,q); \\ 3 if S=k1 then \\ 4 return q; \\ 5 else if Sk1 then \\ 6 small (S,k); \\ 7 else \\ 8 small (L,k1S); \\ \hline \end{tabular} a. What is the worst case running time of this algorithm? The next few subquestions will determine the expected running time of small (A,k). Here, we assume that the element q in Step 1 is chosen uniformly at random, i.e., each element has probability 1 to be the pivot element. Let T(n) be the running time of small (A,k), when A=n. Note that T(n) is non-decreasing in n. Moreover, let Xi be the event that the selected element q in Step 1 is the i th smallest element. You may use the fact, without proving it, that T(n) and Xi are independent random| variables. b. Show that T(n)i=1k1XiT(max{i,ni})+i=kn1Xi+1T(max{i,ni})+cn. Hint: Note that imax{i,ni} and nimax{i,ni}. c. Show that E[T(n)]n2i=n/2n1E[T(i)]+cn. d. Show that E[T(1)]O(1). Show that E[T(n)]O(n), using induction