Calculation of Mean and Variance of Number of Comparisons used by the Randomized Quick Sort Algorithm

Sumit Kumar Jha

Abstract

We calculate the mean and variance of the number of comparisons used by the randomized QuickSort algorithm by the approach of Kirschenhofer, Prodinger, and Tichy to analyze Knuth's In Situ permutation algorithm. This approach helps in calculating these quantities with less computation.

Introduction

QuickSort remains one of the most efficient and widely used sorting algorithms in computer science. Its performance, however, is inherently probabilistic, depending on the choice of pivots and the initial distribution of the input data. To rigorously understand its behavior, researchers focus on the "moments" of the number of comparisons performed—specifically the mean (average-case complexity) and the variance (a measure of performance stability).

While these statistical properties were established decades ago by Donald Knuth and others, traditional derivations often rely on solving complex, nested recurrences. This paper presents a more streamlined mathematical framework, adapting a technique originally designed for "in-situ" permutations to provide an elegant and computationally efficient derivation of QuickSort’s mean and variance.

Methodology: From Recurrences to Differential Equations

The primary innovation of this work lies in shifting the analysis from discrete summations to the domain of calculus and generating functions. The approach follows several key stages:

1. Probability Generating Functions (PGF)

The analysis begins by defining a probability generating function $G_n(z)$: $$G_n(z) = \sum_{k} p_{n,k} z^k$$ where $p_{n,k}$ is the probability that the algorithm performs exactly $k$ comparisons for an array of size $n$.

2. The Double Generating Function

To analyze the algorithm across all possible array sizes simultaneously, the author introduces a "double" generating function $H(z, u)$: $$H(z, u) = \sum_{n \ge 0} G_n(z) \frac{u^n}{n!}$$ This function encapsulates the entire probabilistic behavior of QuickSort within a single mathematical object.

3. Functional Differential Equations

The recursive structure of QuickSort—where an array is partitioned into two independent sub-problems—is transformed into a Partial Differential Equation (PDE): $$\frac{\partial H(z, u)}{\partial u} = z^2 \cdot H^2(z, zu)$$ This transformation is the core of the Kirschenhofer-Prodinger-Tichy approach. Solving this PDE is often more systematic and less error-prone than unrolling deep, nested recurrences.

4. Extraction of Moments

By performing a Taylor expansion of $H(z, u)$ around $z=1$, the author extracts "factorial moments." These moments serve as a mathematical bridge, allowing for the straightforward calculation of the standard mean and variance.

Key Results

The application of this method successfully re-derives the classic formulas for QuickSort performance:

  • Mean Number of Comparisons: The average performance is confirmed as $E[X_n] = 2((n + 1)H_n - n)$, where $H_n$ represents the $n$-th harmonic number.
  • Variance: The variance is expressed through a complex formula involving $n^2$ and the second-order harmonic number $H_n^{(2)}$.
  • Generalization: The paper provides a general "recipe" (Theorem 2.3) for calculating any $s$-th moment. This suggests that higher-order statistics like skewness or kurtosis could be derived using the same framework, provided one computes the necessary higher-order derivatives.

Discussion and Structural Connections

A significant insight of this research is the identification of structural similarities between different algorithmic problems. The specific PDE derived for QuickSort also appears in the analysis of total path lengths in Binary Search Trees (BSTs) and Digital Search Trees. This reveals a deep underlying mathematical connection between these fundamental data structures and the QuickSort algorithm.

Conclusion

By utilizing the generating function approach of Kirschenhofer, Prodinger, and Tichy, this paper demonstrates that the statistical properties of QuickSort can be derived with greater elegance and less algebraic taxation than traditional methods. While the study assumes a uniform distribution of input and focuses on a standard pivot strategy, the framework itself is robust and ripe for application to other recursive algorithms and complex data structures.

Summary updated

Abstract

We calculate the mean and variance of number of comparisons used by the randomized quick sort algorithm by the approach of Kirschenofer, Prodinger and Tichy to analyze Knuth's In Situ permutation algorithm. This approach helps in calculating these quantities with less computation.
BibTeX
@misc{jha2016calculation,
  author = {Sumit Kumar Jha},
  title = {{Calculation of Mean and Variance of Number of Comparisons used by the Randomized Quick Sort Algorithm}},
  year = {2016},
  eprint = {1609.01870},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1609.01870},
}
Figure