Skip to content
GATEiit

GATE DA 2026 Q15: Expected-time recurrence for randomised-input quicksort

Question

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

Let T(n)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)T(n) in this scenario?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: D (official GATE 2026 final answer key)

Concept used: Expected cost: average over every possible rank of the pivot.

First step: For random input the first element is equally likely to be any rank kk, giving subproblems of sizes kk and n−k−1n - k - 1.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 DA question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Programming, Data Structures and Algorithms PYQs

PracticePractise Programming, Data Structures and Algorithms questions →Full paperAll GATE DA 2026 questions →