GATE CS 2001 Q1.14 — Searching, Sorting, Hashing

In Randomized Quicksort, the pivot element is selected uniformly at random from the subarray. This randomization helps avoid the worst-case behavior on already sorted or nearly sorted inputs in practice.

However, the worst-case complexity is defined as the maximum time taken over any possible sequence of choices. In the absolute worst-case scenario, the random number generator might repeatedly select the minimum (or maximum) element as the pivot at every recursive step.

This results in highly unbalanced partitions of sizes $0$ and $n-1$. The recurrence relation for this worst-case scenario is:

$$T(n) = T(n-1) + \Theta(n)$$

Solving this recurrence yields $T(n) = \Theta(n^2)$. Thus, the worst-case time complexity of randomized quicksort remains $O(n^2)$.