Problem Statement
What causes Quick Sort to have O(n^2) worst-case time complexity?
Explanation
Quick Sort degrades to O of n squared when the pivot selection consistently creates unbalanced partitions. The worst case occurs when the pivot is always the smallest or largest element, resulting in partitions of size 0 and n minus 1.
This happens with already sorted or reverse sorted arrays when using the first or last element as pivot. Each partition step only removes one element, creating n levels of recursion with O of n work at each level, giving O of n squared total time. Using random pivot selection or median-of-three method helps avoid this worst case and maintains O of n log n average performance.
Code Solution
SolutionRead Only
// Quick Sort worst case:
// Array: [1, 2, 3, 4, 5] (sorted)
// Pivot: last element (5)
// Partition 1: [1,2,3,4] | [5]
// Pivot: 4
// Partition 2: [1,2,3] | [4] | [5]
// Pivot: 3
// Partition 3: [1,2] | [3] | [4] | [5]
// ...
// n partitions with O(n) work each = O(n^2)
// Balanced partitions (best case):
// [1,2,3,4,5,6,7,8]
// Pivot: 4
// [1,2,3] | [4] | [5,6,7,8]
// log n levels with O(n) work = O(n log n)
// Prevention:
int choosePivot(arr, low, high) {
// Random pivot
int random = low + rand() % (high - low + 1);
return random;
// Median-of-three
int mid = (low + high) / 2;
return medianOf(arr[low], arr[mid], arr[high]);
}Practice Sets
This question appears in the following practice sets:
