Consider Quick sort algorithm used to sort an array of n distinct randomly ordered element. 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 current subarray. Which of the following option represents T(n) in this scenario.
Solution :
The correct option is:
Step-by-step Explanation:
1. Understanding Quick Sort Partitioning:
In the Quick sort algorithm, we choose a pivot element to partition the subarray of size n. Here, the pivot is chosen as the first element of the current subarray. Since the array contains n distinct elements that are randomly ordered, the chosen pivot is equally likely to end up in any of the sorted positions from index 0 to index n - 1. Specifically, the pivot will partition the array into two subarrays: one of size K (representing elements smaller than the pivot) and one of size n - K - 1 (representing elements larger than the pivot), where K can range from 0 to n - 1 with equal probability.
2. Probability of Pivot Position:
Since the input elements are randomly ordered, each possible size of the left subarray, K (where 0 ≤ K ≤ n - 1), occurs with equal probability:
3. Formulating the Recurrence Relation for Expected Time:
For a fixed partition index K, the time taken to sort the subarray is the sum of:
- The time to sort the left subarray of size K, which is T(K)
- The time to sort the right subarray of size n - K - 1, which is T(n - K - 1)
- The linear time required to perform the partitioning, denoted as O(n)
To find the expected time T(n), we take the weighted average over all possible values of K from 0 to n - 1:
Factoring out the constant probability factor
gives the final expected recurrence relation:
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
A comprehensive CUET UG Mathematics Question Paper with Solutions – 2 June 2023 (Shift 3) designed to help students practice and understand the actual CUET exam pattern. This paper covers important topics from Algebra, Calculus, Coordinate Geometry, Probability, Statistics, Matrices, Determinants, and Vectors, featuring a balanced mix of conceptual, numerical, and application-based questions. Detailed solutions are provided to strengthen problem-solving skills, improve conceptual clarity, and enhance calculation accuracy. Based on the CUET syllabus and previous year exam trends, this paper is ideal for practice, revision, self-assessment, time management, previous year analysis, and final preparation for upcoming CUET UG Mathematics examinations.
A comprehensive CUET Accountancy Question Paper – 20 June 2023 (Shift 2) designed to help students practice and analyze previous year exam patterns for effective CUET preparation. This paper covers important topics including Accounting for Partnership Firms, Company Accounts, Financial Statements Analysis, Cash Flow Statements, Accounting Ratios, and Fundamental Accounting Principles. It features a balanced mix of conceptual, numerical, and application-based questions to strengthen accounting concepts, improve calculation accuracy, and enhance problem-solving skills. Based on the CUET exam structure and syllabus, this paper is ideal for practice, revision, self-assessment, time management, previous year analysis, and final preparation for upcoming CUET Accountancy examinations.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.