Worst case of quicksort, and when does it happen?
Options
- O(n log n) on average, and never worse on any input
- O(n²) when pivots are bad, like a sorted input (Correct option)
- O(n) when the input array is already sorted
- O(log n) when the pivot is always the median
Answer
O(n²), with consistently bad pivots (e.g. first element on already sorted input)
Why
Quicksort picks a pivot, puts smaller items on its left and larger on its right, then sorts each side.
If the pivot is always the smallest or largest item (e.g. picking the first element of an already sorted list), one side is empty every time, so it does n + (n-1) + ... steps = O(n²).
Random pivots or median-of-three make that extremely unlikely. Python's sorted uses Timsort, which is O(n log n) in the worst case.
Remember
Quicksort: O(n log n) average, O(n²) with bad pivots.