The GATE Grind

GATE 2026 DA – Question 15

Programming, Data Structures and Algorithms · Divide and conquer: mergesort and quicksort · 1 mark · Multiple choice

Consider that the quick sort algorithm is used to sort an array of $n$ distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the current subarray.

Let $T(n)$ denote the expected time to sort the array. Assume that the time to partition is linear in the size of the current subarray.

Which of the following recurrence relations correctly represents $T(n)$ in this scenario?

  1. $T(n) = T(1) + T(n-1) + O(n)$
  2. $T(n) = T\left(\frac{n}{4}\right) + T\left(\frac{3n}{4}\right) + O(n)$
  3. $T(n) = 2T\left(\frac{n}{2}\right) + O(n)$
  4. $T(n) = \frac{1}{n}\sum_{k=0}^{n-1}\left[T(k) + T(n-k-1)\right] + O(n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $T(n) = \frac{1}{n}\sum_{k=0}^{n-1}\left[T(k) + T(n-k-1)\right] + O(n)$

Explanation

With a random input and the first element as the pivot, the pivot is equally likely to end at any of the $n$ positions. If it ends at position $k$, the two sub-problems have sizes $k$ and $n - k - 1$. Averaging over the $n$ choices of $k$ and adding the linear partition cost gives the recurrence in option D. The other options describe the worst case (A) or fixed splits (B and C).