GATE CS 2009 Q39 — Searching, Sorting, Hashing

In the given quick-sort variant, the pivot is always chosen as the $\left(n/4\right)^{\text{th}}$ smallest element using an $O(n)$ time selection algorithm. This guarantees a consistent split ratio of at least $1:3$ at every step of the recursion.

The recurrence relation for the worst-case time complexity $T(n)$ is:

Where:

• $T\left(\frac{n}{4}\right)$ and $T\left(\frac{3n}{4}\right)$ represent the time to recursively sort the two partitioned subarrays.
• $\Theta(n)$ is the time taken to find the $(n/4)^{\text{th}}$ smallest element and partition the array around it.

We can solve this recurrence using the recursion tree method:

1. At the root (level 0), the cost is $cn$.
2. At level 1, the subproblems have sizes $\frac{n}{4}$ and $\frac{3n}{4}$. The total cost is $c\left(\frac{n}{4}\right) + c\left(\frac{3n}{4}\right) = cn$.
3. At any level $i$, the sum of the sizes of all subproblems is at most $n$, meaning the total work done at each level is bounded by $cn$.
4. The recursion stops when the subproblem size reduces to $1$. The longest path in the tree corresponds to repeatedly taking the larger fraction $\frac{3}{4}$, which gives a maximum depth of: $$\log_{4/3} n = \Theta(\log n)$$

Multiplying the work per level by the maximum depth of the tree:

Since the depth is at least $\log_{4} n = \Theta(\log n)$, we also have $T(n) \ge \Theta(n \log n)$. Thus, the worst-case time complexity is $\Theta(n \log n)$.