arXiv:1609.01870v6 [cs.DS] 21 Oct 2016

Revisiting calculation of moments of number of comparisons
used by the randomized quick sort algorithm
Sumit Kumar Jha
Preprint of the following paper in
Discrete Mathematics, Algorithms and Applications:
http://www.worldscientific.com/doi/pdf/10.1142/S179383091750001X
Abstract. We revisit the method of Kirschenhofer, Prodinger and Tichy to calculate the moments of number of comparisons used by the randomized quick sort algorithm. We reemphasize
that this approach helps in calculating these quantities with less computation. We also point
out that as observed by Knuth this method also gives moments for total path length of a binary
search tree built over a random set of n keys.

1. Introduction
Consider the following variant of quick sort algorithm from [9]: the quick sort algorithm
recursively sorts numbers in an array by partitioning it into two smaller and independent subarrays,
and thereafter sorting these parts. The partitioning procedure chooses the last element in the array
as pivot and puts it in its right place where numbers to the left of it are smaller than it, and those
to its right are larger than it.
For purposes of this analysis assume that the input array to the quick sort algorithm contains
distinct numbers which are randomly ordered. We may assume the input to the algorithm is
simply a permutation of {1, 2, · · · , n} (if the input array has n elements).
Let Sn be the set of all n! permutations of {1, 2, · · · , n}. Consider a uniform probability
distribution on the set Sn , and define for all σ ∈ Sn , Cn (σ) to be the number of comparisons used
to sort σ by the quick sort algorithm. We wish to calculate mean and variance of Cn over the
uniform distribution on Sn .
Our aim here is to obtain following [6] [5]
Theorem 1.1 (Knuth [8]). We have
Mean(Cn ) = 2((n + 1)Hn − n);
and
Var(Cn ) = 7n2 − 4(n + 1)2 Hn(2) − 2(n + 1)Hn + 13n,
over the uniform probability distribution on Sn . Here we have used the notation Hn =
Pn
(2)
and Hn = k=1 k12 .

Pn

1
k=1 k

Before proceeding we would like to point out that Hennequin [3] has computed the first
five cumulants of the number of comparisons of Quicksort. Also, the variance of the number of
comparisons of Quicksort is computed in [4].
2. Calculation of mean and variance
Let an,s be the number of permutations of n elements requiring a total of s comparisons to
sort by the procedure of quicksort.
1

2

SUMIT KUMAR JHA

We start by defining the corresponding probability generating function:
X an,k z k
Gn (z) =
.
n!
k≥0

Theorem 2.1. For n ≥ 1
(2.1)

Gn (z) =

z n+1 X
Gn−j (z)Gj−1 (z),
n
1≤j≤n

and
(2.2)

G0 (z) = 1.

Proof. The first partitioning stage requires n + 1 comparisons (for some other variants this
might be n − 1). If the pivot element is kth largest, then the sub arrays after partitioning are of
sizes k − 1 and n − k. Thus we can write
X n − 1 
X
an−k,i ak−1,j .
(2.3)
an,s =
k−1
1≤k≤n

i+j=s−(n+1)

s

Multiplying equation (2.3) by z and dividing by n! we get
X zs
X
an−k,i
ak−1,j
ans z s
=
·
n!
n
(n − k)! (k − 1)!
1≤k≤n
i+j=s−(n+1)
o
X zs n
=
· coefficient of z s−(n+1) in Gn−k (z) · Gk−1 (z)
n
1≤k≤n

n
o
X z n+1
=
· z s−(n+1) coefficient of z s−(n+1) in Gn−k (z) · Gk−1 (z)
n
1≤k≤n

after which summing on s gives us equation (2.1).



We will now consider the double generating function H(z, u) defined by
X
(2.4)
H(z, u) =
Gn (z)un .
n≥0

Corollary 2.2. We have
∂H(z, u)
= z 2 · H 2 (z, zu),
∂u

(2.5)
and

H(1, u) = (1 − u)−1 .

(2.6)

Proof. From equation (2.1) we have
X
X
∂H(z, u)
= z2
(uz)n−1
Gn−j (z)Gj−1 (z)
∂u
n≥1
1≤j≤n
X

= z2
(uz)n−1 · coefficient of (uz)n−1 in H(z, uz) · H(z, uz)
n≥1

= z 2 · H(z, zu) · H(z, zu).
Equation (2.6) follows from the fact that Gn (1) = 1.



Now we write the sth factorial moments βs (n) of the random variable with the aid of the
probability generating function Gn (z):
 s

d
(2.7)
βs (n) =
G
(z)
.
n
dz s
z=1

REVISITING CALCULATION OF MOMENTS OF NUMBER OF COMPARISONS

3

The generating functions fs (u) of βs (n) are
(2.8)

fs (u) =

X

βs (n)un .

n≥0

By Taylor’s formula and equation (2.7) we get
X
(z − 1)s
fs (u)
(2.9)
H(z, u) =
.
s!
s≥0

Theorem 2.3. For integer s ≥ 0 we have
(k)

X

fs0 (u) = s! ·

(2.10)

i+j+k+l+m=s

(m)

ai · fj (u) · fl (u) · uk+m
,
j! · k! · l! · m!

where

1



2
ak =

1



0

if
if
if
if

k
k
k
k

= 0;
= 1;
= 2;
> 2.

Proof. Using Taylor’s theorem we can write
fj (x) =

X fj(k) (u)(x − u)k
k!

k≥0

which on substituting x = uz gives
(2.11)

fj (uz) =

X fj(k) (u)(z − 1)k uk

.

k!

k≥0

Now substituting equation (2.9) in equation (2.5) gives:
X
X
(z − 1)p X
(z − 1)r
(z − 1)s
= z2 ·
fp (uz)
·
fr (uz)
fs0 (u)
s!
p!
r!
p≥0

s≥0

=

X
i≥0

ai (z − 1)i ·

X (z − 1)p X
p≥0

p!

(m)
− 1)l ul X (z − 1)r X fr (u)(z − 1)m um
·
l!
r!
m!
r≥0

l≥0

=

X

r≥0

(l)
fp (u)(z

X

(z − 1)h

h≥0

ai ·

i+j+k+l+m=h

where in the second last line we replaced z 2 by
both sides of the equation gives

P

i≥0

= s! ·

X
i+j+k+l+m=s

1
·
j!

k!

(m)

·

1 fl
·
l!

(u) um
m!

ai (z − 1)i . Now comparing coefficients on

(k)

fs0 (u)

m≥0

(k)
fj (u) uk

(m)

ai · fj (u) · fl (u) · uk+m
.
j! · k! · l! · m!


Remark 2.4. For asymptotic theory of differential equations originating here we recommend
reader the paper [1].
Corollary 2.5. We have
(2.12)
(2.13)

f0 (u) = (1 − u)−1 ,
f1 (u) =

2
1
log
,
(1 − u)2
1−u

4

SUMIT KUMAR JHA

(2.14) f2 (u) =

6
6
8 log2 (1 − u) 8 log(1 − u) 4 log2 (1 − u) 12 log(1 − u)
−
−
+
+
−
.
3
3
2
2
3
(1 − u)
(1 − u)
(1 − u)
(1 − u)
(1 − u)
(1 − u)2

Proof. The equation (2.12) follows from the fact that β0 (n) = 1 for all n ≥ 0.
Setting s = 1 in equation (2.10) gives
(0)

(0)

(1)

(0)

(1)

(0)

f10 (u) = a1 · f0 (u) · f0 (u) + f0 (u) · f0 (u) · u + f0 (u) · f0 (u) · u
(0)

(0)

(0)

(0)

+f1 (u) · f0 (u) + f0 (u) · f1 (u)
u
u
f1 (u)
2
f1 (u)
+
+
+
=
+
,
(1 − u)2
(1 − u)3
(1 − u)3
(1 − u) (1 − u)
where we used the fact that f0 (u) = (1 − u)−1 . The above equation is
f10 (u) −

(2.15)

2
2f1 (u)
2u
+
.
=
3
1−u
(1 − u)
(1 − u)2

Solving the linear differential equation (2.15) by multiplying with integrating factor (1 − u)2 gives
f1 (u) =

1
2
1
2
log
+ f1 (0) =
log
.
(1 − u)2
1−u
(1 − u)2
1−u

Plugging s = 2 in (2.10) and solving the resultant differential equation gives
f2 (u) =

8 log2 (1 − u) 8 log(1 − u) 4 log2 (1 − u) 12 log(1 − u)
6
6
−
−
+
+
−
.
(1 − u)3
(1 − u)3
(1 − u)2
(1 − u)2
(1 − u)3
(1 − u)2


Corollary 2.6. We have
β1 (n) = 2((n + 1)Hn − n),
and
β2 (n) = 4(n + 1)2 (Hn2 − Hn(2) ) + 4(n + 1)2 Hn − 8(n + 1)Hn + 8nHn − 4nHn (5 + 3n) + 11n2 + 15n.
Proof. We use following expansions from [2]

 X


1
1
n+m n
log
=
(Hn+m − Hm )
u ;
(1 − u)m+1
1−u
n
n≥0

1
log2
(1 − u)m+1



1
1−u


=

X

2

((Hn+m − Hm ) −

(2)
(Hn+m

−

(2)
Hm
))



n≥0


n+m n
u ,
n

to conclude the assertion.



Proof of Theorem 1.1. We conclude the results after noting
Mean(Cn ) = β1 (n),
Var(Cn ) = β2 (n) − (β1 (n))2 + β1 (n).

3. Similar Partial Differential Functional Equations
We point out that following two examples from [7] can be analyzed using the method employed
here:
1. Moments of total path length Ln of a binary search tree built over a random set of n
keys can be extracted from the
∂L(z, u)
∂L(0, u)
= L2 (zu, u),
= 1,
∂z
∂z
P
where L(z, u) = n≥0 Ln (u)z n is the bivariate generating function.

REVISITING CALCULATION OF MOMENTS OF NUMBER OF COMPARISONS

5

2. A digital search tree for which the bivariate generating function L(z, u) satisfies


∂L(z, u)
1
2
=L
zu, u ,
∂z
2
with L(z, 0) = 1.
References
[1] Hua-Huai Chern1, Hsien-Kuei Hwang, and Tsung-Hsi Tsai. An asymptotic theory for cauchy-euler differential
equations with applications to the analysis of algorithms. http://www.stat.sinica.edu.tw/chonghi/Papers/
An_asymptotic_theory_for_Cauchy-Euler_differential_equations.pdf, 2002.
[2] Daniel H. Greene and Donald E. Knuth. Mathematics for the Analysis of Algorithms: Modern Birkhuser
Classics. Birkhauser Basel, 3rd edition, 2007.
[3] Pascal Hennequin. Analyse en moyenne d’algorithmes, tri rapide et arbres de recherche. http://algo.inria.
fr/AofA/Research/src/Hennequin.PhD.html/, 1991.
[4] Vasileios Iliopoulos. The quicksort algorithm and related topics. http://repository.essex.ac.uk/13266/, 2013.
[5] P. Kirschenhofer, H. Prodinger, and R.F. Tichy. Ober einige funktionaldifferentialgleichungen aus der analyse
von algorithmen. http://math.sun.ac.za/~hproding/pdffiles/hlawka_funktionalgleichungen.pdf.
[6] P. Kirschenhofer, H. Prodinger, and R.F. Tichy. A contribution to the analysis of in situ permutation. Glasnik
Mathematicki, 22(42):269–278, 1987.
[7] Charles Knessl and Wojciech Szpankowskit. Quicksort algorithm again revisited. http://docs.lib.purdue.edu/
cgi/viewcontent.cgi?article=2351&context=cstech, 1997.
[8] Donald E. Knuth. The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching. Addison
Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.
[9] Robert Sedgewick and Kevin Wayne. Algorithms. Addison-Wesley Professional, 4th edition, 2011.
Center for Security, Theory, and Algorithmic Research, International Institute of Information
Technology, Hyderabad, India
E-mail address: kumarjha.sumit@research.iiit.ac.in

