We are going to derive an upper bound for the average number of exchanges for quicksort. A similar analysis would give a lower bound, giving the high order term exactly.

(a) Assume that the partition (or pivot) element ends up in position q. How many exchanges does partition do, NOT counting the final exchange where the pivot element is placed in its proper sorted position? Briefly justify. Note that an element can exchange with itself.

(b) Write a recurrence for the expected number of exchanges (for quicksort), NOT counting the final exchange where pivot element is placed in its proper sorted position.

(c) Simplify the recurrence as much as reasonably possible (as we did in class for comparisons).

(d) Guess that the solution is at most an In n for some constant a. Use constructive induction to verify the guess and derive the constant a.

(e) Give an upper bound on how many exchanges involve the pivot element thoughout all of the partitions in the entire quicksort algorithm. Briefly justify.

(f) Add this value to your answer in Part (d) to get an upper bound on the total number of exchanges.

(g) Rewrite your solution using log base 2 rather than the natural log, evaluating the constant to three decimal places.