(b) (5 pts) Give the recurrence relation for this version of QuickSort and solve for its asymptotic solution. Also, give some intuition (in English) about how the indecisive Partition algorithm changes the running time of QuickSort.

1. Suppose that instead of a randomized QuickSort we implement an indecisive QuickSort, where the Partition function alternates between the best and the worst cases. You may assume that IndecisivePartition works correctly (that is, it produces a list in which the first i elements are all r, the (i 1)-st element is r, and the remaining elements are all 2 x, where r is the pivot and i is what it has to be) and takes O(n) time on a list of length n (a) (5 pts) Prove the correctness of this version of QuickSort