Randomized quicksort is an extension of quicksort where the pivot is chosen…
2001
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?
- A.
O(n)
- B.
O(n*log(n))
- C.
O(n2)
- D.
O(n!)
Attempted by 41 students.
Show answer & explanation
Correct answer: C
Randomized quicksort improves upon standard quicksort by selecting a random pivot, which makes the worst-case scenario highly unlikely in practice. However, the theoretical worst-case time complexity remains O(n2).
This occurs if the random pivot consistently selects the smallest or largest element at every step, resulting in unbalanced partitions of size 0 and n-1. In such a case, the recursion depth becomes n, leading to O(n2) comparisons overall. While randomized quicksort guarantees an expected time complexity of O(n log n), the worst-case bound is not eliminated, only made improbable.