Question:medium
Consider the quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists, one of which contains one-fifth of the elements and the remaining elements are contained in the other sub-list. Let T(n) be the number of comparisons required to sort n elements. Then:
Consider the quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists, one of which contains one-fifth of the elements and the remaining elements are contained in the other sub-list. Let T(n) be the number of comparisons required to sort n elements. Then:
Show Hint
In recurrence relations, always include the partitioning cost (e.g., n) along with recursive calls for sub-problems.
Updated On: Feb 11, 2026
- T(n) ≤ 2T(n/5) + n
- T(n) ≤ T(n/5) + T(4n/5) + n
- T(n) ≤ 2T(4n/5) + n
- T(n) ≤ 2T(n/2) + n
Show Solution
The Correct Option is B
Solution and Explanation
Quicksort's time complexity is dictated by its partitioning method. For example, when the pivot divides the list into sections of n/5 and 4n/5 elements, the resulting recurrence relation is T(n) = T(n/5) + T(4n/5) + n. The 'n' term signifies the cost of the partitioning step, which involves comparing all n elements.
Was this answer helpful?
0
Top Questions on Algorithm
- When does the worst case of binary search occur?
- Suppose that insertion sort is applied to the array \([1,2,3,5,7,9,11,x,15,13]\) and it takes exactly 2 swaps to sort the array. Select all possible values of \( x \).
- Which of the following data structures supports binary search in \( O(\log n) \) time complexity?
- Consider the following algorithm:
What will be the output (O/P) of this algorithm? - Want to practice more? Try solving extra ecology questions todayView All Questions