GATE CS 2008 Q43 — Searching, Sorting, Hashing

In the Quicksort algorithm, the list of size $n$ is partitioned into two sub-lists around a pivot element. The cost of this partitioning step is $O(n)$ comparisons (represented here as $n$).

We are given that each of the two resulting sub-lists contains at least one-fifth of the elements. Let the sizes of the two sub-lists be $n_1$ and $n_2$. This condition implies:

In the worst-case scenario that satisfies this condition, the split is as unbalanced as possible. This occurs when one sub-list is of the minimum possible size, $\frac{n}{5}$, and the other sub-list is of the maximum possible size, $\frac{4n}{5}$.

Therefore, the recurrence relation for the number of comparisons $T(n)$ is bounded by:

Hence, the correct option is B.