1.What would be the complexity of Quicksort if the pivot is always the median? (Assume the median can always be found in linear time).?

a. Always O(n log n)

b. Always O(n^2 )

c. Worst case: O(n^2 ), average case: O(n log n)

d. Worst case: O(n^2 log n), average case: O(n^2 )

Given a pre-sorted array of unique integers, what is the expected running time of Quicksort if the pivot is always chosen to be either the first or last element?

a. O(n log n)

b. O(n^2 log n)

c. O(n^2 )

d. None of the above

please give a short explanation for each question, thank you!