ITPEC FE Morning October 2021 Question 5

Quicksort Time Complexity — average vs worst case for randomized quicksort.

Randomized quicksort selects the pivot randomly:

• •Average case: O(n log n) — random pivot tends to split the array roughly in half
• •Worst case: O(n²) — pivot consistently lands on the min or max element (rare but possible)

Why not others:
- (a) O(n) worst case is impossible for any comparison-based sort (lower bound is O(n log n))
- (c) O(n² log n) average is too high — quicksort averages O(n log n)
- (d) O(n² log n) average is too high for the same reason

Key rule: Randomization improves quicksort's expected performance but does not change the theoretical worst case of O(n²).

AI-generated — may contain errors