1- What is the worst-case running time of Quicksort if the pivot is randomly chosen as the first element in the array. Explain.

2- Show that the average size of aleft is (n-1)/2 when the input to Quicksort is n distinct elements and the median M is randomly chosen from one of the elements.

3- Calculate the running time of a divide-and-conquer algorithm that requires three recursive calls (each with input-size n/2) and 3n 2 steps that include dividing the input, and using the three solutions to obtain the final solution.