✏️ Explanatory Question
What is the worst-case behaviour of QuickSort in terms of the number of comparisons?
What is the worst-case behaviour of QuickSort in terms of the number of comparisons?
Ans. In the worst case, poor pivot selection can cause QuickSort to perform:
(n − 1) + (n − 2) + … + 2 + 1 = n(n − 1)/2 comparisons
Therefore, its worst-case time complexity is O(n2).
💡 Explanation:
The worst case occurs when the selected pivot is repeatedly the smallest or largest element in the current subarray.
Each partition then places only the pivot in its final position and leaves the remaining n − 1 elements in one subarray. Thus, the partition sizes become:
n − 1, n − 2, n − 3, …, 2, 1
The total number of comparisons is the sum:
(n − 1) + (n − 2) + … + 1 = n(n − 1)/2 = (n2 − n)/2
In Big-O notation, constants and lower-order terms are removed. Therefore:
O((n2 − n)/2) = O(n2)
Memory tip: Repeatedly balanced partitions give O(n log n), whereas repeatedly one-sided partitions give O(n2).