Algorithms

Consider the following strategy for choosing a pivot element for the Partition subroutine of QuickSort, applied to an array A.

Let n be the number of elements of the array A

If n<=15, perform an Insertion Sort of A and return

Otherwise:

- Choose 2[sqrt(n)] elements at random from n; let S be the new list with the chosen elements.

- Sort the list S usin Insertion Sort and use the median m of S as a pivot element

- Partition using m as a pivot

- Carry out quickSort recursively on the two parts

(c) Write a recurrence relation for the worst case running time of QuickSort with this pivoting strategy.

Please show detailed understanding of the problem. Incorrect or lazy illusration to solving the problem will result in penalty. Its only one question. Thank You!!!

(Part a&b) of this problem is posted on another thread.