Question

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?

• A. \(T(n) = T(1) + T(n-1) + O(n)\)
• B. \(T(n) = T\left(\dfrac{n}{4}\right) + T\left(\dfrac{3n}{4}\right) + O(n)\)
• C. \(T(n) = 2T\left(\dfrac{n}{2}\right) + O(n)\)
• D. \(T(n) = \dfrac{1}{n}\displaystyle\sum_{k=0}^{n-1} \left[T(k) + T(n-k-1)\right] + O(n)\)

Hint:

Random input means the pivot's rank after partitioning is uniformly distributed over 0 to n-1, so average \(T(k)+T(n-1-k)\) over all k.

Answer 1

The Correct Option is D

The key word in this question is "expected", not "worst case" or "best case". That single word tells us we need to average over every possible way the pivot could split the array, rather than picking one fixed scenario.

Here is the setup: quicksort always grabs the first element of the current subarray as pivot. If the array were sorted or reverse sorted, that would always give the smallest or largest element, a very lopsided split of size $1$ and $n-1$. But this array is randomly ordered, so nothing forces the first element to be extreme, it is just as likely to be any rank in the array.

Formally, after we partition around the pivot, say $k$ elements land in the left part and $n-1-k$ land in the right part. Because the ordering is random, $k$ can be $0, 1, 2, \dots, n-1$ with equal probability $\frac{1}{n}$ each, there's no reason for any particular split to be favored over another.

Now build the expected cost. For a fixed $k$, the total work is $T(k)$ to sort the left part, $T(n-k-1)$ to sort the right part, plus the linear partition cost. Since we do not know $k$ in advance and every value is equally likely, we take the average across all $n$ possibilities:

\[ T(n) = \frac{1}{n}\sum_{k=0}^{n-1}\Big(T(k) + T(n-k-1)\Big) + O(n) \]

Let's summarize why the other three do not fit:

• $T(n) = T(1) + T(n-1) + O(n)$ is the worst-case recurrence, forcing the smallest possible split every time, which only happens for sorted or adversarial input, not random input.
• $T(n) = T(n/4) + T(3n/4) + O(n)$ and $T(n) = 2T(n/2) + O(n)$ both lock in one specific fixed ratio for every single partition. A random array with a first-element pivot does not guarantee any fixed ratio call after call, the ratio itself is random and must be averaged over, not assumed constant.

Averaging over all $n$ equally likely split points is what genuinely captures "expected time" here, and that is exactly the recurrence in option (D).

\[ \boxed{T(n) = \frac{1}{n}\sum_{k=0}^{n-1}\left[T(k)+T(n-k-1)\right] + O(n)} \]