Question:
Which of the following recurrence relations represents the average case time complexity of QuickSort?
Which of the following recurrence relations represents the average case time complexity of QuickSort?
Show Hint
QuickSort worst case: \( T(n) = T(n-1) + O(n) \).
QuickSort average case: Expected recurrence over all pivot positions.
Updated On: Feb 15, 2026
- \( T(n) = T(n/4) + T(3n/4) + O(n) \)
- \( T(n) = 2T(n/2) + O(n) \)
- \( T(n) = \frac{1}{n} \sum_{k=0}^{n-1} \left[ T(k) + T(n-k-1) \right] + O(n) \)
- \( T(n) = T(1) + T(n-1) + O(n) \)
Hide Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
Step 1: Understand QuickSort behavior.
QuickSort chooses a pivot and partitions the array into two parts.
If pivot position is \( k \), then recursive calls are: \[ T(k) \quad \text{and} \quad T(n-k-1). \] Step 2: Consider average case.
In average case, pivot can appear at any position from \( 0 \) to \( n-1 \) with equal probability.
Therefore, we take the expected value over all possible splits: \[ \frac{1}{n} \sum_{k=0}^{n-1} \left[ T(k) + T(n-k-1) \right]. \] Step 3: Add partition cost.
Partitioning takes linear time: \[ O(n). \] Thus, average case recurrence becomes: \[ T(n) = \frac{1}{n} \sum_{k=0}^{n-1} \left[ T(k) + T(n-k-1) \right] + O(n). \] Step 4: Compare options.
(A) Represents a specific split (not average).
(B) Represents Merge Sort.
(C) Matches expected recurrence for QuickSort.
(D) Represents worst case when pivot is smallest/largest.
Hence, option (C) is correct.
QuickSort chooses a pivot and partitions the array into two parts.
If pivot position is \( k \), then recursive calls are: \[ T(k) \quad \text{and} \quad T(n-k-1). \] Step 2: Consider average case.
In average case, pivot can appear at any position from \( 0 \) to \( n-1 \) with equal probability.
Therefore, we take the expected value over all possible splits: \[ \frac{1}{n} \sum_{k=0}^{n-1} \left[ T(k) + T(n-k-1) \right]. \] Step 3: Add partition cost.
Partitioning takes linear time: \[ O(n). \] Thus, average case recurrence becomes: \[ T(n) = \frac{1}{n} \sum_{k=0}^{n-1} \left[ T(k) + T(n-k-1) \right] + O(n). \] Step 4: Compare options.
(A) Represents a specific split (not average).
(B) Represents Merge Sort.
(C) Matches expected recurrence for QuickSort.
(D) Represents worst case when pivot is smallest/largest.
Hence, option (C) is correct.
Was this answer helpful?
0
0
Top Questions on Data Structures and Algorithms
- In a Binary Search Tree, which traversal method produces the elements in non-decreasing order?
- CUET (PG) - 2026
- Data Science
- Data Structures and Algorithms
- Which data structure is used by the system to implement recursion?
- CUET (PG) - 2026
- Data Science
- Data Structures and Algorithms
- What is the time complexity of building a heap from an unsorted array of size \(n\)?
- CUET (PG) - 2026
- Data Science
- Data Structures and Algorithms
- P = [1, 2, 3, 5, 4]
Two sorting algo Binary sort (BS), Insertion sort (IS) apply. Let N$_1$ be the total number of comparisons done by BS on the element of P and N$_2$ be the total number of comparisons done by IS on the elements of P. Which of the following option is/are correct?- GATE DA - 2026
- Data Science and Artificial Intelligence
- Data Structures and Algorithms
- Consider the 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 cycle but there is no self-loop, further G may not be strongly connected. Let G$^R$ be the graph obtained by reversing direction of all edges without changing set of vertices. Assume that BFS or DFS for any given vertex V of a graph will visit only the reachable vertices from V in that graph. Which of the following statement must always be true regardless of the structure of G?
- GATE DA - 2026
- Data Science and Artificial Intelligence
- Data Structures and Algorithms
View More Questions
Questions Asked in GATE DA exam
- Rishi and Swathi are students of Class 5. Pavan and Tanvi are students of Class 4. Rishi and Pavan are boys. Swathi and Tanvi are girls. These four students played a total of three games of chess. The games were played one after another. A player who lost a game did not participate in any more games. It was observed that:
1. The first game was the only game where two students of the same class played against each other.
2. The students of Class 5 won more games than the students of Class 4.
3. The boys won 2 games and the girl won 1 game.
The student who did not lose any game is:- GATE DA - 2026
- Logical Reasoning
Consider two distinct positive numbers \( m, n \) with \( m > n \). Let \[ x = n^{\log_n m}, \quad y = m^{\log_m n}. \] The relation between \( x \) and \( y \) is -
- GATE DA - 2026
- Logarithms
- Consider the supervised learning task. The objective function being minimized is \( f(w) = w \cdot x \), where \( w \in \mathbb{R} \) is the parameter. Stochastic Gradient Descent with learning rate of 0.10. Let \( w = 10.00 \) be the \( i^{\text{th}} \) iteration (\( w_i \)). The value of \( w \) at the end of iteration \( (i+1) \) is if \( x = 10 \) ________. Round off 2 decimal.
- GATE DA - 2026
- Machine Learning
- The value of \[ \sum_{j=0}^{\infty} \sum_{i=1}^{\infty} 2^{-j} 3^{-i} \] is ________.
- GATE DA - 2026
- Sequences and Series
- Consider the Ridge LRR is being used to learn prediction function \( y_{\text{pred}} = w^T x \) where \( w, x \in \mathbb{R}^2 \) & mean absolute error (MAE) is used to measure the prediction error. A weight of 0.20 is associated with the regularizer. At an intermediate step of training process assume that the parameter \( w = [-3.00, 4.00]^T \). In the next step for the I/P \( x = [1.00, 2.00]^T \), the predicted value of \( y \) is noted. Let the relation b/w \( x = [x_1, x_2]^T \) & the true value of \( y \) be \( y_{\text{true}} = x_1 + x_2 \). The value of the overall regularized loss for instance is __________ (upto 2 decimal).
- GATE DA - 2026
- Machine Learning
View More Questions