The analysis of the expected running time of randomized quicksort in Section 7.4.2 assumes that all element values are distinct. In this problem, we examine what happens when they are not. a. Suppose that all element values are equal. What would be randomized quicksort’s running time in this case? b. The PARTITION procedure returns an index q such that each element of AŒp : : q 1 is less than or equal to AŒq and each element of AŒq C 1::r is greater than AŒq. Modify the PARTITION procedure to produce a procedure PARTITION0 .A; p; r/, which permutes the elements of AŒp : : r and returns two indices q and t, where p q t r, such that all elements of AŒq : : t are equal, each element of AŒp : : q 1 is less than AŒq, and each element of AŒt C 1::r is greater than AŒq. Like PARTITION, your PARTITION0 procedure should take ‚.r p/ time. c. Modify the RANDOMIZED-QUICKSORT procedure to call PARTITION0 , and name the new procedure RANDOMIZED-QUICKSORT0 . Then modify the QUICKSORT procedure to produce a procedure QUICKSORT0 .p; r/ that calls Problems for Chapter 7 187 RANDOMIZED-PARTITION0 and recurses only on partitions of elements not known to be equal to each other. d. Using QUICKSORT0 , how would you adjust the analysis in Section 7.4.2 to avoid the assumption that all elements are distinct?