Algorithms and Data Structures · Middle · Question 3 of 75
What is the worst case of quicksort and when does it happen?
- ✓Correct answer: O(n²), when pivots keep splitting the array very unevenly
- 2O(n log n), when the array contains many duplicates
- 3O(n), when the input happens to be already sorted
Explanation
If the pivot is always the smallest or largest element (for example, the first element of a sorted array), each partition removes only one element. Random pivots or median-of-three make this unlikely; the average is O(n log n).