Exercise 6.9.

In randomized QuickSort (Algorithm 13), given an element

X in the input array:

1. What is the maximum number of comparisons that x is involved (i.e., the number of times x is compared with other elements) during the

course of the algorithm?

2. What is the minimum number of comparisons that x is involved during the course of the algorithm?

3. What is the average number of comparisons that x is involved during the course of the algorithm?

Justify your answers.

Algorithm 13:

Algorithm 13 Algorithm Randomized Quicksort. Input: A set S. Output: The set S in sorted order. 1: if Sl