Asymptotic expressions for moments of number of comparisons used by the randomized quick sort algorithm.

Sumit Kumar Jha

Abstract

We calculate asymptotic expansions for the moments of the number of comparisons used by the randomized quick sort algorithm using the singularity analysis of certain generating functions.

Introduction

Quicksort is one of the most fundamental and widely utilized algorithms in computer science. While its average-case complexity of $O(n \log n)$ is a staple of undergraduate curricula, a rigorous statistical characterization of the algorithm requires a deeper investigation into its higher-order moments. The "first moment" provides the expected performance, but the second and subsequent moments are essential for understanding the variance, skewness, and kurtosis of the algorithm's runtime distribution.

This paper provides a unified mathematical derivation for these moments by applying the principles of analytic combinatorics. Specifically, we utilize the singularity analysis of generating functions to produce precise asymptotic expansions that describe the statistical behavior of Quicksort as the input size $n$ approaches infinity.

Methodology

The analytical approach follows a multi-step pipeline designed to transform a discrete recursive problem into a continuous analytical one:

1. Probability Generating Functions (PGFs)

We define $G_n(z)$ as a polynomial where the coefficient of $z^k$ represents the probability that Quicksort requires exactly $k$ comparisons for an input of size $n$. This encapsulates the entire probability distribution into a single mathematical object.

2. Functional Differential Equations

The recursive nature of the Quicksort algorithm—partitioning an array into two sub-problems based on a pivot—is translated into a partial differential equation (PDE). By defining a "double" generating function $H(z, u)$, the recursive structure is captured by the equation: $$\frac{\partial H(z, u)}{\partial u} = H^2(z, zu)$$ This transformation allows the use of calculus to solve what is fundamentally a counting problem.

3. Factorial Moments

To simplify the derivation, the author focuses on factorial moments, denoted as $\beta_s(n)$. Factorial moments are often more mathematically tractable than raw moments when working with derivatives of PGFs, as they relate directly to the $s$-th derivative of $G_n(z)$ evaluated at $z=1$.

4. Singularity Analysis

The core technical tool employed is the singularity analysis framework established by Flajolet and Odlyzko. By analyzing the behavior of the generating functions as they approach their singularities (typically at $u=1$), we can map the "blow-up" characteristics of the function to the asymptotic growth rates of the underlying sequences. This provides a rigorous path from the functional equation to a closed-form asymptotic expansion.

Key Theoretical Insights

The Role of Mathematical Constants

The analysis reveals that the second-order terms of the expansion are intimately linked to fundamental mathematical constants. Specifically, the $s$-th Harmonic number ($H_s$) and Euler’s constant ($\gamma \approx 0.57721$) emerge naturally from the expansion. This highlights a deep connection between the efficiency of basic sorting and the structure of harmonic series.

Unified Expansion Structure

The paper demonstrates that for any integer $s \geq 1$, the $s$-th moment follows a consistent structural pattern: a dominant leading term of $n^s \log^s n$, followed by a correction term of $n^s \log^{s-1} n$. This uniformity allows for a generalized understanding of the algorithm's tail behavior.

Results

The primary result of this research is the derivation of the asymptotic expansion for the $s$-th factorial moment $\beta_s(n)$ for integers $s \geq 1$:

$$\beta_s(n) = 2^s n^s \log^s n + 2^s s(\gamma - 2)n^s \log^{s-1} n + O(n^s \log^{s-2} n)$$

This formula provides the necessary precision to calculate the statistical properties of Quicksort for arbitrarily large $n$.

  • For $s=1$: The formula simplifies to the well-known average number of comparisons, approximately $2n \ln n$.
  • For $s=2$: The expansion provides the basis for calculating the variance, which describes how much the actual number of comparisons might deviate from the average in a given run.

Discussion and Limitations

While this paper provides a rigorous foundation for the statistical analysis of Quicksort, several constraints remain:

  1. Distribution Assumptions: The analysis assumes a uniform distribution of input permutations, which is the standard model for randomized Quicksort. It does not explicitly model performance on non-randomized inputs that are already nearly sorted, though randomization of the pivot typically brings the performance in line with these results.
  2. Pivot Strategies: The derivation assumes a standard single-pivot strategy. Modern implementations, such as the Dual-Pivot Quicksort used in the Java standard library, utilize different partitioning logic that would require a modified generating function and would likely result in different constants within the expansion.
  3. Expansion Depth: The current expansion is provided up to the $O(n^s \log^{s-2} n)$ term. While this is highly precise for most computational needs, the methodology used here could theoretically be extended to derive even lower-order terms if higher precision were required for specific theoretical applications.

Conclusion

By bridging the gap between discrete algorithm analysis and complex analysis, this work provides a definitive asymptotic expansion for the moments of Quicksort. These results not only confirm existing knowledge regarding the average-case performance but also provide the tools necessary to analyze the stability and reliability of the algorithm through its higher-order statistical moments.

Summary updated

Abstract

We calculate asymptotic expansions for the moments of number of comparisons used by the randomized quick sort algorithm using the singularity analysis of certain generating functions.
BibTeX
@misc{jha2016asymptotic,
  author = {Sumit Kumar Jha},
  title = {{Asymptotic expressions for moments of number of comparisons used by the randomized quick sort algorithm.}},
  year = {2016},
  eprint = {1610.05656},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1610.05656},
}
Figure