Algorithms and Data Structures · Senior · Question 68 of 75
What does randomization give quicksort?
- 1Stability for elements with equal keys
- ✓Correct answer: Expected O(n log n) for every input
- 3A guaranteed O(n log n) worst case for all input
Explanation
With a random pivot no fixed input is consistently bad, so the expectation holds for any input, including adversarial ones. The worst case is still possible, just extremely unlikely.