3. Suppose that we modify the Partition algorithm in QuickSort in such a way that on alternating levels of the recursion tree, Partition either chooses the best possible pivot or the worst possible pivot. (a) Given an array, what choice of pivot will result in the best partitioning, and which one will result in the worst partitioning?

(b) Write down a recurrence relation for this version of QuickSort, and solve it asymptotically. Show your work. Assume that the time it takes to find the pivot (either best or worst, depending on the level of recursion) is (n) for lists of length n.

(c) Provide a verbal explanation of how this Partition algorithm affects the running time of QuickSort, in comparison with the case where the best possible pivot is always used.

(d) Suppose now we modify the Partition algorithm in QuickSort in such a way that the algorithm chooses the worst possible pivot for two levels of recursion, then the best possible pivot at the next level, then the worst possible pivot for the next two levels, then the best possible pivot, and so on. What is your estimate of the asymptotic running time? Provide a verbal justification of your estimate.

3. Suppose that we modify the Partition algorithm in QuickSort in such a way that on alternating levels of the recursion tree, Partition either chooses the best possible pivot or the worst possible pivot. (a) Given an array, what choice of pivot will result in the best partitioning, and which one will result in the worst partitioning? (b) Write down a recurrence relation for this version of QuickSort, and solve it asymp- totically. Show your work. Assume that the time it takes to find the pivot (either best or worst, depending on the level of recursion) is e(n) for lists of length n. (c) Provide a verbal explanation of how this Partition algorithm affects the running time of QuickSort, in comparison with the case where the best possible pivot is always used. (d) Suppose now we modify the Partition algorithm in QuickSort in such a way that the algorithm chooses the worst possible pivot for two levels of recursion, then the best possible pivot at the next level, then the worst possible pivot for the next two levels, then the best possible pivot, and so on. What is your estimate of the asymptotic running time? Provide a verbal justification of your estimate. 3. Suppose that we modify the Partition algorithm in QuickSort in such a way that on alternating levels of the recursion tree, Partition either chooses the best possible pivot or the worst possible pivot. (a) Given an array, what choice of pivot will result in the best partitioning, and which one will result in the worst partitioning? (b) Write down a recurrence relation for this version of QuickSort, and solve it asymp- totically. Show your work. Assume that the time it takes to find the pivot (either best or worst, depending on the level of recursion) is e(n) for lists of length n. (c) Provide a verbal explanation of how this Partition algorithm affects the running time of QuickSort, in comparison with the case where the best possible pivot is always used. (d) Suppose now we modify the Partition algorithm in QuickSort in such a way that the algorithm chooses the worst possible pivot for two levels of recursion, then the best possible pivot at the next level, then the worst possible pivot for the next two levels, then the best possible pivot, and so on. What is your estimate of the asymptotic running time? Provide a verbal justification of your estimate