GATE 2026 DA Q.15: solution and answer

Official answer: DSource: Official answer key, GATE 2026 DA (IIT Guwahati)

1. Because the input is randomly ordered and the pivot is the first element of the current subarray, the pivot is equally likely to have any rank $1,2,\dots ,n$ in that subarray. This holds again in every recursive call, because each subarray of a random permutation is itself randomly ordered.

2. If the pivot has rank $k+1$, partitioning leaves $k$ elements on the left and $n-k-1$ on the right, for $k=0,1,\dots ,n-1$. Each of these $n$ splits has probability $\frac{1}{n}$.

3. Partitioning scans the current subarray once, so its cost is $O(n)$ (given in the question as linear in the subarray size).

4. The expected time is the partition cost plus the expected cost of the two subproblems, averaged over all splits:

   $$T(n)=\frac{1}{n}\sum _{k=0}^{n-1}\left[T(k)+T(n-k-1)\right]+O(n).$$

5. Option (A) is a single fixed split of sizes $1$ and $n-1$, the extreme case of always picking a minimum or maximum pivot. It is not an expected value. Options (B) and (C) fix the split at $\frac{1}{4}:\frac{3}{4}$ or $\frac{1}{2}:\frac{1}{2}$, which assumes the pivot always lands at one chosen position. Only option (D) averages over every possible split with equal probability, so it is the recurrence for the expected time. The answer is (D).