For randomized quicksort sorting n distinct elements, the expected number of key comparisons is 2(n + 1)H_n − 4n, where H_n is the nth harmonic number. Its asymptotic expected comparison count is approximately 2n ln n.
Quicksort Expected Comparison Count
For randomized quicksort sorting n distinct elements, the expected number of key comparisons is 2(n + 1)H_n − 4n, where H_n is the nth harmonic number. Its asymptotic expected comparison count is approximately 2n ln n.
\(E[C_{\mathrm{n}}] = 2(n + 1)H_{\mathrm{n}} - 4n\)
What this formula means
Scientific principle
Principle
Randomized quicksort selects a pivot, partitions the elements into smaller and larger groups, and recursively sorts those groups. The probability that any two elements are compared depends on whether one of them is selected as a pivot before an element between their sorted ranks is selected.
Derivation
1. Consider n distinct elements arranged by sorted rank.
2. Let Xᵢⱼ equal 1 if the elements with ranks i and j are compared, and 0 otherwise.
3. Two elements are compared only if the first pivot selected from the rank interval i through j is one of its endpoints.
4. The probability of this event is 2/(j − i + 1).
5. By linearity of expectation, E[C_n] = Σᵢ<ⱼ 2/(j − i + 1).
6. Grouping terms by the rank difference and simplifying gives E[C_n] = 2(n + 1)H_n − 4n.
7. Since H_n ≈ ln n + γ for large n, expected comparisons grow as Θ(n log n).
Final Result
E[C_n] = 2(n + 1)H_n − 4n
Harmonic Number
H_n = 1 + 1/2 + 1/3 + ⋯ + 1/n
Asymptotic Relation
E[C_n] ≈ 2n ln n + O(n)
Expected Complexity
Θ(n log n)
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
E[C_n] | Expected number of key comparisons | Comparison operations |
n | Number of distinct input elements | Elements |
H_n | nth harmonic number | Dimensionless |
γ | Euler–Mascheroni constant, approximately 0.57721 | Dimensionless |
SI units and conversions
Comparison Count
Dimensionless operation count
Harmonic Number
Dimensionless
Input Size
Number of elements
Asymptotic Complexity
Θ(n log n)
Conditions of use
The input contains n distinct keys.
The pivot is selected uniformly at random, or the pivot-selection process produces the equivalent random ordering assumption.
The partition operation uses key comparisons.
The expression describes expected comparisons over the pivot-selection randomness.
Limitations and assumptions
The formula is not the worst-case comparison count.
Worst-case quicksort complexity is Θ(n²), for example when partitions repeatedly have sizes 0 and n − 1.
Duplicate keys and three-way partitioning can change the comparison-count analysis.
The exact expected count depends on the partition scheme and comparison-count convention.
Expected Θ(n log n) time does not mean every execution takes Θ(n log n) time.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
Calculate the expected number of comparisons for randomized quicksort sorting 3 distinct elements. |
| The expected comparison count is approximately 2.67. |
Estimate the expected comparison count for randomized quicksort with 4 distinct elements. |
| The expected comparison count is approximately 6.83. |
Real-world applications
Analysis of randomized sorting algorithms
Performance estimation for in-memory sorting
Algorithm design and benchmarking
Expected-case complexity analysis
Comparison of sorting strategies
Formula Meaning
For randomized quicksort sorting n distinct elements, the expected number of key comparisons is 2(n + 1)H_n − 4n, where H_n is the nth harmonic number. Its asymptotic expected comparison count is approximately 2n ln n.
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.