We are trying to optimise the pivot section of the Quicksort algorithm. For our pivot choice, we are using an algorithm to find the median of an unsorted list. The algorithm we opt to use for this takes O$($n$)$ time, where n is the size of the list we are partitioning. This would make the overall worst$-$case time complexity of Quicksort as O$($nlogn$).$ Why don't we use this approach in general?

Question $3$Answer

a$.$

While the linear overhead of finding the median is not visible in the asymptotic description, we assume it to be too large to be practical

b$.$

This is a better approach and we should use it

c$.$

We would have to sort the list before we can calculate the median

d$.$

There's no algorithm to calculate the median in O$($n$)$ time