✦ScienexySCIENCE KNOWLEDGE LIBRARY
General science · SCI-FORM-COM-2068

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

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.

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

SymbolMeaningUnit

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

ProblemSolutionAnswer

Calculate the expected number of comparisons for randomized quicksort sorting 3 distinct elements.

  • Given: n = 3.

  • H₃ = 1 + 1/2 + 1/3 = 11/6.

  • Use: E[C_n] = 2(n + 1)H_n − 4n.

  • E[C₃] = 2(4)(11/6) − 4(3).

  • E[C₃] = 44/3 − 12.

  • E[C₃] = 8/3 ≈ 2.67.

The expected comparison count is approximately 2.67.

Estimate the expected comparison count for randomized quicksort with 4 distinct elements.

  • Given: n = 4.

  • H₄ = 1 + 1/2 + 1/3 + 1/4 = 25/12.

  • E[C₄] = 2(5)(25/12) − 4(4).

  • E[C₄] = 250/12 − 16.

  • E[C₄] = 41/6 ≈ 6.83.

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.

← Back to Formula Hub · Suggest a correction or source