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?
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?
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?
Show 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.
Updated On: Jul 22, 2026
- \(T(n) = T(1) + T(n-1) + O(n)\)
- \(T(n) = T\left(\dfrac{n}{4}\right) + T\left(\dfrac{3n}{4}\right) + O(n)\)
- \(T(n) = 2T\left(\dfrac{n}{2}\right) + O(n)\)
- \(T(n) = \dfrac{1}{n}\displaystyle\sum_{k=0}^{n-1} \left[T(k) + T(n-k-1)\right] + O(n)\)
Show Solution
Verified By Collegedunia
The Correct Option is D
Solution and Explanation
Step 1: Understand what makes this the expected time, not the worst case.
The array is randomly ordered, and the pivot is always taken as the first element of whatever subarray we are currently sorting. Because the input order is random, we cannot assume the pivot always lands in a fixed spot like the smallest or the middle element, instead, the pivot could equally likely end up being the smallest, the largest, or anything in between, once we finish partitioning.
Step 2: Work out the distribution of the pivot's final rank.
After partitioning around the pivot, suppose \(k\) elements end up smaller than the pivot (forming the left subarray of size \(k\)) and the remaining \(n-1-k\) elements end up larger (forming the right subarray of size \(n-1-k\)). Since the array is randomly ordered, the first element is equally likely to be any of the \(n\) elements in terms of rank, so \(k\) is equally likely to be any value from 0 up to \(n-1\), each with probability \(\frac{1}{n}\).
Step 3: Build the recurrence by averaging over all possible splits.
Given a particular value of \(k\), the cost is \(T(k) + T(n-1-k)\) for sorting the two resulting parts, plus \(O(n)\) for the partition step itself (given as linear in the current subarray size). Since every split value \(k\) from 0 to \(n-1\) is equally likely, the expected time is the average of \(T(k) + T(n-1-k)\) over all these \(n\) equally likely outcomes, plus the partition cost:
\[ T(n) = \frac{1}{n}\sum_{k=0}^{n-1}\left[T(k) + T(n-k-1)\right] + O(n) \]
This matches option (D) exactly.
Step 4: Why the other options fail.
Option (A), \(T(n) = T(1) + T(n-1) + O(n)\), describes the worst case, where the pivot always ends up smallest or largest, giving one part of size 1 every single time, this happens only for already sorted or specially adversarial inputs, not for a randomly ordered array. Options (B) and (C) both assume a single fixed split ratio, one quarter-three quarters, or half-half, happens on every single call. But with a random array and a first-element pivot, the actual split ratio varies from call to call, we cannot pin it to one fixed ratio, we must average across every possible ratio, which is exactly what option (D) does.
Step 5: Final Answer.
The correct recurrence for the expected time is option (D). \[ \boxed{T(n) = \frac{1}{n}\sum_{k=0}^{n-1}\left[T(k)+T(n-k-1)\right] + O(n)} \]
The array is randomly ordered, and the pivot is always taken as the first element of whatever subarray we are currently sorting. Because the input order is random, we cannot assume the pivot always lands in a fixed spot like the smallest or the middle element, instead, the pivot could equally likely end up being the smallest, the largest, or anything in between, once we finish partitioning.
Step 2: Work out the distribution of the pivot's final rank.
After partitioning around the pivot, suppose \(k\) elements end up smaller than the pivot (forming the left subarray of size \(k\)) and the remaining \(n-1-k\) elements end up larger (forming the right subarray of size \(n-1-k\)). Since the array is randomly ordered, the first element is equally likely to be any of the \(n\) elements in terms of rank, so \(k\) is equally likely to be any value from 0 up to \(n-1\), each with probability \(\frac{1}{n}\).
Step 3: Build the recurrence by averaging over all possible splits.
Given a particular value of \(k\), the cost is \(T(k) + T(n-1-k)\) for sorting the two resulting parts, plus \(O(n)\) for the partition step itself (given as linear in the current subarray size). Since every split value \(k\) from 0 to \(n-1\) is equally likely, the expected time is the average of \(T(k) + T(n-1-k)\) over all these \(n\) equally likely outcomes, plus the partition cost:
\[ T(n) = \frac{1}{n}\sum_{k=0}^{n-1}\left[T(k) + T(n-k-1)\right] + O(n) \]
This matches option (D) exactly.
Step 4: Why the other options fail.
Option (A), \(T(n) = T(1) + T(n-1) + O(n)\), describes the worst case, where the pivot always ends up smallest or largest, giving one part of size 1 every single time, this happens only for already sorted or specially adversarial inputs, not for a randomly ordered array. Options (B) and (C) both assume a single fixed split ratio, one quarter-three quarters, or half-half, happens on every single call. But with a random array and a first-element pivot, the actual split ratio varies from call to call, we cannot pin it to one fixed ratio, we must average across every possible ratio, which is exactly what option (D) does.
Step 5: Final Answer.
The correct recurrence for the expected time is option (D). \[ \boxed{T(n) = \frac{1}{n}\sum_{k=0}^{n-1}\left[T(k)+T(n-k-1)\right] + O(n)} \]
Was this answer helpful?
0
0
Top GATE DA Data Science and Artificial Intelligence Questions
- Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to u. Let (u, v) be an edge in G such that d[u] < d[v]. If the edge (u, v) is explored first in the direction from u to v during the above DFS, then (u, v) becomes a _____ edge.
- Three fair coins are tossed independently. T is the event that two or more tosses result in heads. S is the event that two or more tosses result in tails. What is the probability of the event T ∩ S?
- Consider the matrix \(M=\begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\).
Which ONE of the following statements is TRUE ? - For any twice differentiable function ƒ: R → R, if at some x* ∈ R, f'(x*) = 0 and f'(x*) > 0, then the function f necessarily has a ______ at x = x*.
Note : R denotes the set of real numbers. - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables
View More Questions
Top GATE DA Data Structures and Algorithms Questions
Given the Python code:
- You are given the following Pre-order and In-order traversals of a Binary Tree \(T\) with nodes E, F, G, P, Q, R, S.
Pre-order: P Q S E R F G
In-order: S Q E P F R G
Which of the following statements is/are true about the Binary Tree \(T\)? - Let \(A\) be a sorted array containing 1000 distinct integers. You perform a recursive binary search on \(A\) to find an element \(y\). Suppose each comparison checks whether the middle element computed during the current recursive step is equal to, less than, or greater than \(y\).
The maximum number of comparisons that may have to be performed if \(y\) is not an element of \(A\) is __________. (Answer in integer) - Consider a directed graph \(G = (V, E)\), where \(V\) is the finite set of vertices and \(E\) is the set of directed edges between the vertices. \(G\) may contain cycles but there is no self-loop. Further, \(G\) may not be strongly connected.
Let \(G^R\) be the graph obtained by reversing the directions of all the edges in \(G\) without changing the set of vertices.
Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex \(v\) of a graph visits only the reachable vertices from \(v\) in that graph.
Which of the following statements must always be true, regardless of the structure of \(G\)?
Top GATE DA Questions
- Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to u. Let (u, v) be an edge in G such that d[u] < d[v]. If the edge (u, v) is explored first in the direction from u to v during the above DFS, then (u, v) becomes a _____ edge.
- Three fair coins are tossed independently. T is the event that two or more tosses result in heads. S is the event that two or more tosses result in tails. What is the probability of the event T ∩ S?
- Consider the matrix \(M=\begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\).
Which ONE of the following statements is TRUE ? - For any twice differentiable function ƒ: R → R, if at some x* ∈ R, f'(x*) = 0 and f'(x*) > 0, then the function f necessarily has a ______ at x = x*.
Note : R denotes the set of real numbers. - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables
View More Questions