GATE DA 2026 — Question 15

Programming, Data Structures and Algorithmsdivide and conquer: mergesort, quicksortMCQ1 mark · −1/3 if wrongMedium

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. A
    \(T(n) = T(1) + T(n - 1) + O(n)\)
  2. B
    \(T(n) = T\left(\frac{n}{4}\right) + T\left(\frac{3n}{4}\right) + O(n)\)
  3. C
    \(T(n) = 2T\left(\frac{n}{2}\right) + O(n)\)
  4. D
    \(T(n) = \frac{1}{n}\sum_{k=0}^{n-1}[T(k) + T(n - k - 1)] + O(n)\)
Practise the full 2026 paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on divide and conquer: mergesort, quicksortTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group