GATE CS 2006 Q52 — Searching, Sorting, Hashing

When the median of $n$ elements is selected as the pivot in Quick Sort, the array is always partitioned into two equal (or nearly equal) halves of size approximately $\lfloor n/2 \rfloor$.

The recurrence relation for the time complexity $T(n)$ is given by:

We are given that the median can be found in $O(n)$ time. The partitioning step also takes $O(n)$ time. Therefore, the recurrence relation simplifies to:

Applying the Master's Theorem for divide-and-conquer recurrences of the form $T(n) = aT(n/b) + f(n)$:

• $a = 2$, $b = 2$
• $n^{\log_b a} = n^{\log_2 2} = n^1 = n$
• Since $f(n) = \Theta(n)$, we fall into Case 2 of the Master's Theorem.

Thus, the solution to the recurrence is:

Hence, the correct option is B.