Randomised quick sort improves on plain quick sort because
Ait eliminates the worst case entirely; every run is Θ(n log n)
Bit switches to merge sort when the input is sorted
Cit sorts in O(n) on any input
Da random pivot makes bad splits unlikely, giving expected Θ(n log n)
Answer & Solution
Correct answer: D. a random pivot makes bad splits unlikely, giving expected Θ(n log n)
Randomisation makes the algorithm's running time depend on its own coin flips, not on the input. Sorted inputs no longer trigger the worst case. Worst case is still O(n²) in theory but astronomically unlikely. Switching to merge sort is a different hybrid (introsort); plain randomised quick sort cannot beat the Ω(n log n) comparison bound.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for