Problem 4. In the runtime analysis of the Random Quicksort algorithm in lecture (textbook section 2.5, p 37), we assumed, for simplicity, that each of the elements in the input were unique. That is, yi < yi+1 < < yj1 < yj . From that, we concluded that yi is chosen as a pivot before any other in the set Y ij = {yi , yi+1, . . . , yj1, yj} with probability 1/|Y ij | = 1/(j i + 1). Similarly, the probability that yj is chosen as a pivot before any other element in Y ij is also 1/(j i + 1). 1

(a) Now, lets remove the assumption that every element is unique. In particular, yi yi+1 yj1 yj is all we know. Why does the reasoning above not work anymore? (Hint: provide an example where the probability is incorrect)

(b) Indicate a slight change in the way we stated the Random Quicksort algorithm, or a slight change in the analysis, so that we can still conclude that Pr(yi and yj were compared) is still exactly 2/ ji+1 .