GATE 2026 Data Science & AI Q15

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?

Accepted Answer

T(n) = (1/n) Σ_{k=0}^{n-1} [T(k) + T(n - k - 1)] + O(n)

Answer

T(n) = T(1) + T(n - 1) + O(n)

Answer

T(n) = T (n/4) + T (3n/4) + O(n)

Answer

T(n) = 2T (n/2) + O(n)