ITPEC FE Morning October 2021 Question 5
When sorting an array of n elements by using a randomized version of the quicksort algorithm, where the pivot is selected randomly, which of the following shows the average-case and the worst-case time complexities? Here, big-O notation, O(x), is used to denote the growth rate.
Explanation
Average O(n log n), worst O(n²) — a random pivot makes bad splits unlikely, but not impossible.
On average a random pivot splits the array into reasonably balanced parts, so there are about log n levels of partitioning, each costing O(n) comparisons: O(n log n) in total.
If every chosen pivot happens to be the smallest or largest element, each pass removes only one element, and n + (n − 1) + … + 1 comparisons give O(n2). Randomization makes that case very unlikely for any input, but it can still occur.
Answer (b)
Why not others:
- •(a) — an O(n) worst case is below the O(n log n) lower bound for any comparison sort, and a worst case cannot be faster than the average
- •(c) — pairs an average that is too high with a worst case smaller than the average, which is impossible
- •(d) — an O(n2 log n) average would exceed the O(n2) worst case; an average can never be above the worst case
Key rule: Randomizing the pivot protects quicksort against specific bad inputs, but its worst case stays O(n2); only the chance of hitting it changes.
Algorithm and Programming · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.