Final answer:
When the median is chosen as a pivot in Quick Sort, it ensures each partition of the sort is balanced. This results in Quick Sort having a complexity of d. O(n log n), which is option d in the given choices.
Step-by-step explanation:
The median of n elements can be found in O(n) time, and when this median is used as a pivot in the Quick Sort algorithm, the complexity of the algorithm can significantly improve. In the case that the median is always chosen as a pivot, Quick Sort will effectively divide the input array into two equal halves with each recursive call.
This means that the height of the recursion tree will be proportional to the logarithm of the number of elements, leading to a balanced partition.
Normally, the Quick Sort algorithm has a best-case time complexity of O(n log n) when the partitions are balanced and a worst-case time complexity of O(n²) when the partitions are unbalanced (for instance, when the pivot is the least or the greatest element).
However, when the median is used as a pivot, the case of unbalanced partitions is eliminated. Therefore, the Quick Sort algorithm will consistently perform at its best-case scenario, as each partition will be balanced, and the algorithm will have a time complexity that is linearithmic.
Considering this, the correct option in the final answer reflecting the complexity of Quick Sort using the median as a pivot is d. ⊝(n log n).