arXiv:1508.07230v2 [math.PR] 26 Sep 2015

ON THE TAILS OF THE LIMITING QUICKSORT
DISTRIBUTION
SVANTE JANSON
Abstract. We give asymptotics for the left and right tails of the limiting Quicksort distribution. The results agree with, but are less precise
than, earlier non-rigorous results by Knessl and Spankowski.

1. Introduction
Let Xn be the number of comparisons used by the algorithm Quicksort
when sorting n distinct numbers, initially in a uniformly random order.
Equivalently, Xn is the internal pathlength in a random binary search tree
with n nodes. (See e.g. Knuth [7, Sections 5.2.2 and 6.2.2] or Drmota [1,
Chapter 8 and Section 1.4.1] for a description of the algorithm and of binary search trees.) It follows that Xn satisfies the distributional recurrence
relation
d

∗
Xn = XUn −1 + Xn−U
+ n − 1,
n

n ≥ 1,

(1.1)

d

where = denotes equality in distribution, and, on the right, Un is distributed
d
uniformly on the set {1, . . . , n}, Xj∗ = Xj , X0 = 0, and Un , X0 , . . . , Xn−1 ,
∗
are all independent. (Thus, (1.1) can be regarded as a definiX0∗ , . . . , Xn−1
tion of Xn .)
It is well-known, and easy to show from (1.1), that
E Xn = 2(n + 1)Hn − 4n ∼ 2n ln n,
Pn

(1.2)

−1 is the n:th harmonic number. Moreover, it was
where Hn :=
k=1 k
proved by Régnier [9] and Rösler [10], using different methods, that the
normalized variables
Xn − E Xn
(1.3)
Zn :=
n
converge in distribution to some limiting random variable Z, as n → ∞.
There is no simple description of the distribution of Z, but various results have been shown by several different authors. For example, Z has an
everywhere finite moment generating function, and thus all moments are
finite [10], with E Z = 0 and Var Z = 7 − 23 π 2 ; furthermore, Z has a density

Date: 28 August, 2015; minor revision 26 September, 2015.
Partly supported by the Knut and Alice Wallenberg Foundation.
1

2

SVANTE JANSON

which is infinitely differentiable [11; 2]. Moreover, the recurrence relation
(1.1) yields in the limit a distributional identity, which can be written as
d

Z = U Z ′ + (1 − U )Z ′′ + g(U ),

(1.4)
d

where U , Z ′ and Z ′′ are independent, U ∼ U(0, 1) is uniform, Z ′ , Z ′′ = Z,
and g is the deterministic function
g(u) := 2u ln u + 2(1 − u) ln(1 − u) + 1.

(1.5)

Furthermore, Rösler [10] showed that (1.4) together with E Z = 0 and
Var Z < ∞ determines the distribution of Z uniquely; see further [3]. The
identity (1.4) is the basis of much of the study of Z, including the present
work.
In the present paper we study the asymptotics of the tail probabilities
P(Z 6 −x) and P(Z > x) as x → ∞. Using non-rigorous methods from
applied mathematics (assuming an as yet unverified regularity hypothesis),
Knessl and Szpankowski [6] found very precise asymptotics of both the left
tail and the right tail. Their result for the left tail is that, as x → ∞, with
γ = (2 − ln12 )−1 ,


P(Z 6 −x) = (c1 + o(1)) exp −c2 eγx = exp −eγx+c3 +o(1) ,
(1.6)
where c1 , c2 , c3 are some constants (c1 is explicit in [6], but not c2 ). For
the right tail, they give a more complicated expression, which by ignoring
higher order terms implies, for example,

P(Z > x) = exp −x ln x − x ln ln x + (1 + ln 2)x + o(x) .
(1.7)

It has been a challenge to justify these asymptotics rigorously, and so far
very little progress has been made. Some rigorous upper bounds were given
by Fill and Janson [4], in particular

P(Z > x) 6 exp −x ln x + (1 + ln 2)x ,
x > 303,
(1.8)
with the same leading term (in the exponent) as (1.7), and for the left tail
P(Z 6 −x) 6 exp(−x2 /5),

x > 0,

(1.9)

which is much weaker than (1.6).
Also the present paper falls short of the (non-rigorous) asymptotics (1.6)–
(1.7) from [6], but we show, by simple methods, the following results, which
at least show that the leading terms in the top exponents in (1.6)–(1.7) are
correct.
Theorem 1.1. (i) Let γ := (2 − ln12 )−1 . As x → ∞,


exp −eγx+ln ln x+O(1) 6 P(Z 6 −x) 6 exp −eγx+O(1)

(1.10)

(ii) As x → ∞,



exp −x ln x − x ln ln x + O(x) 6 P(Z > x) 6 exp −x ln x + O(x) . (1.11)

ON THE TAILS OF THE LIMITING QUICKSORT DISTRIBUTION

3

We show the lower bounds in Sections 3 and 4, and the upper bounds in
Sections 5 and 6. The lower bounds are proved by direct arguments using
the identity (1.4); the upper bounds are proved by the standard method of
first estimating the moment generating function.
Remark 1.2. The right inequality in (1.11) follows from the more precise
(1.8), where an explicit value is given for the implicit constant; we include
this part of (1.11) for completeness. (The proof in Section 6 actually yields a
better constant than (1.8) for large x, see (6.10).) We expect that, similarly,
the implicit constants in the other parts of (1.10)–(1.11) could be replaced by
explicit bounds, using more careful versions of the arguments and estimates
below. However, in order to keep the proofs simple, we have not attempted
this.
Remark 1.3. We consider only the limiting random variable Z, and not Zn
or Xn for finite n. Of course, the results for Z imply corresponding results
for the tails P(Zn 6 −x) and P(Zn > x) for n sufficiently large (depending
on x), but we do not attempt to give any explicit results for finite n. For
some bounds for finite n, see [5] and (for large deviations) [8].
Remark 1.4. Although we do not work with Zn for finite n, the proofs
below of the lower bounds can be interpreted for finite n, saying that we
can obtain Zn 6 −x with roughly the given probability (for large n) by
considering the event that in the first Θ(x) generations, all splits are close
to balanced (with proportions 12 ± x−1/2 , say); similarly, to obtain Zn > x
we let there be one branch of length Θ(x) where all splits are extremely
unbalanced (with at most a fraction (x ln x)−1 on the other side). The fact
that we require an exponential number of splits to be extreme for the lower
tail, but only a linear number for the right tail, can be seen as an explanation
of the difference between the two tails, with the left tail doubly exponential
and the right tail roughly exponential.
2. Preliminaries
Note that g in (1.5) is a continuous convex function on [0, 1], with maximum g(0) = g(1) = 1 and minimum g(1/2) = 1 − 2 ln 2 = −(2 ln 2 − 1) < 0.
Let ψ(t) := E etZ be the moment generating function of Z. As said above,
Rösler [10] showed that ψ(t) is finite for every real t. The distributional
identity (1.4) yields, by conditioning on U , the functional equation
Z 1
tZ
ψ(ut)ψ((1 − u)t)etg(u) du.
(2.1)
ψ(t) := E e =
0

We may replace Z by the right-hand side of (1.4); hence we may without
loss of generality assume the equality (not just in distribution)
Z = U Z ′ + (1 − U )Z ′′ + g(U ).

(2.2)

4

SVANTE JANSON

3. Left tail, lower bound
Proof of lower bound in (1.10). Let ε > 0 be so small that g( 21 + ε) < 0, and
let a := −g( 12 + ε) > 0. For any z, on the event {Z ′ 6 −z, Z ′′ 6 −z, and
|U − 12 | 6 ε}, (2.2) yields
Z 6 −U z − (1 − U )z + g(U ) = −z + g(U ) 6 −z − a.

(3.1)

Hence, for any real z,
P(Z 6 −z − a) > 2ε P(Z 6 −z)2 .

(3.2)

It follows by induction that
P(Z 6 −na) > (2ε)2

n −1

P(Z 6 0)2 ,
n

n > 0.

(3.3)

2n

Consequently, using 2ε 6 1, P(Z 6 −na) > (2ε P(Z 6 0)) , and thus, with
c := ln(2 P(Z 6 0)) > −∞,

ln P(Z 6 −na) > 2n ln ε + c ,
n > 0.
(3.4)

If x > 0, we take n = ⌈x/a⌉ and obtain


ln P(Z 6 −x) > 2x/a+1 ln ε + c .

We choose (for large x) ε = x−1/2 , so, using Taylor’s formula,




a = −g 12 + ε = −g 12 + O ε2 = 2 ln 2 − 1 + O x−1

(3.5)

(3.6)

and thus


a−1 = (2 ln 2 − 1)−1 + O x−1 .

(3.7)

Consequently, (3.5) yields


ln P(Z 6 −x) > 2x/(2 ln 2−1)+O(1) ln x−1/2 + c = −eγx+O(1)+ln ln x .

(3.8)


4. Right tail, lower bound
Proof of lower bound in (1.11). Let 0 < δ < 21 . If 0 < U 6 δ, then
g(U ) > g(δ) = 1 + 2δ ln δ + O(δ) > 1 + 3δ ln δ,

(4.1)

with the last inequality holding provided δ is small enough.
Assume that (4.1) holds, and assume that Z ′ > 0, Z ′′ > z > 0 and U 6 δ.
Then (2.2) yields
Z > (1 − δ)z + g(δ) > z − δz + 1 − 3δ ln δ−1 .

(4.2)

P(Z > z + 1 − δz − 3δ ln δ−1 ) > δ P(Z > 0) P(Z > z).

(4.3)

Consequently,
Let x be sufficiently large and choose δ = 1/(x ln x). Then, for 0 6 z 6 x,
z + 1 − δz − 3δ ln δ−1 > z + 1 −

ln(x ln x)
2
1
−3
>z+1−
,
ln x
x ln x
ln x

(4.4)

ON THE TAILS OF THE LIMITING QUICKSORT DISTRIBUTION

provided x is large enough. Hence, if b := 1 −
then for 0 6 z 6 x we have

2
ln x

5

and c := P(Z > 0) > 0,

P(Z > z + b) > cδ P(Z > z).

(4.5)

By induction, we find for 0 6 n 6 x/b + 1,
P(Z > nb) > cn δn P(Z > 0) = cn+1 δn > (cδ)n+1 .

(4.6)

Consequently, taking n := ⌈x/b⌉,
ln P(Z > x) > (n + 1)(ln c + ln δ) > (x/b + 2)(ln c + ln δ)


= x + O(x/ ln x) − ln x − ln ln x + O(1)
= −x ln x − x ln ln x + O(x).

(4.7)


5. Left tail, upper bound
Lemma 5.1. There exists a > 0 such that for all t > 0, with κ := γ −1 =
2 − ln12 ,

ψ(−t) < exp κt ln t + at + 1 .
(5.1)

Proof. We note that t ln t > −e−1 for t > 0, and thus κt ln t + at + 1 >
−κe−1 + 1 > 0. Since ψ(t) is continuous
and ψ(0) = 1, there exists t1 > 0

such that ψ(−t) < exp 1 − κe−1 for 0 6 t 6 t1 , and thus (5.1) holds for all
such t, and any a > 0. Next, let t2 := πe2 . We may choose a > 0 such that
(5.1) holds for t ∈ [t1 , t2 ].
Before proceeding to larger t, define
h(u) := u ln u + (1 − u) ln(1 − u)

(5.2)

and note that g(u) = 2h(u) + 1 by (1.5).
Now suppose that (5.1) fails for some t > 0 and let T := inf{t > 0 :
(5.1) fails}. Then T > t2 , and, by continuity,

ψ(−T ) = exp κT ln T + aT + 1 .
(5.3)

Furthermore, if 0 < u < 1, then (5.1) holds for t = uT and t = (1 − u)T ,
and thus, recalling (5.2),

ψ(−uT )ψ −(1 − u)T

< exp κuT ln(uT ) + κ(1 − u)T ln((1 − u)T ) + auT + a(1 − u)T + 2


= exp κT ln T + κ u ln u + (1 − u) ln(1 − u) T + aT + 2 .

= exp κT ln T + κh(u)T + aT + 2 .

Furthermore, g(u) = 1 + 2h(u), and thus we obtain


ψ(−uT )ψ −(1 − u)T e−T g(u) 6 exp κT ln T − ((2 − κ)h(u) + 1)T + aT + 2 .
(5.4)

6

SVANTE JANSON

By (5.2), h(u) is a convex function with h( 12 ) = − ln 2, h′ ( 12 ) = 0 and
= u−1 + (1 − u)−1 > 4, and thus by Taylor’s formula, h(u) > − ln 2 +
2(u − 21 )2 . Furthermore, 2 − κ = 1/ ln 2, and thus

h′′ (u)

2
(u − 12 )2 > (u − 12 )2 .
ln 2
Combining (2.1), (5.4), and (5.5), we obtain
Z 1


exp κT ln T + aT + 2 − (u − 12 )2 T du
ψ(−T ) 6
0
Z
 ∞ −(u− 1 )2 T
2
< exp κT ln T + aT + 2
e
du
−∞
r

π
exp κT ln T + aT + 2 .
=
T
(2 − κ)h(u) + 1 >

(5.5)

(5.6)


Since T > t2 = πe2 , this yields ψ(−T ) < exp κT ln T + aT + 1 , which
contradicts (5.3). This contradiction shows that no such T exists, and thus
(5.1) holds for all t > 0.

Proof of upper bound in (1.10). For x > 0 and any t > 0, by Lemma 5.1,

P(Z 6 −x) 6 e−tx E e−tZ = e−tx ψ(−t) < exp −tx + κt ln t + at + 1 . (5.7)

We optimize by taking t = exp(κ−1 (x − a) − 1) and obtain
ln P(Z 6 −x) < t(κ ln t + a − x) + 1 = −κt + 1 = −eκ
which is the upper bound in (1.10) because

κ−1

= γ.

−1 x+O(1)

,

(5.8)


6. Right tail, upper bound
As said in the introduction, (1.8) was proved in [4]. Nevetheless we give
for completeness a proof of the upper bound in (1.11), similar to the proof in
Section 5. (It is also similar to the proof in [4] but simpler, partly because we
do not keep track of all constants and do not try to optimize; nevertheless,
it yields a slight improvement of (1.8) for large x, see (6.10) below.)
Lemma 6.1. There exists a > 0 such that for all t > 0,

ψ(t) 6 exp et + at .

(6.1)

Note that [4, Corollary 4.3] shows the bound ψ(t) 6 exp(2et ) for t > 5.02,
which is explicit, but weaker for large t.
Proof. Since ψ(0) = 1 < e, it follows by continuity that there exists t1 > 0
such that ψ(t) 6 e for t ∈ [0, t1 ], and thus (6.1) holds for t ∈ [0, t1 ] and any
a > 0.
Let t2 := 100, and choose a so that (6.1) holds for t ∈ [t1 , t2 ]. Assume
that (6.1) fails for some t > 0, and let T := inf{t > 0 : (6.1) fails}. Then
T > t2 , and, by continuity,

ψ(T ) = exp eT + aT .
(6.2)

ON THE TAILS OF THE LIMITING QUICKSORT DISTRIBUTION

7

Furthermore, if 0 < u < 1, then (6.1) holds for t = uT and t = (1 − u)T ,
and thus, using (2.1) and the symmetry u ↔ 1 − u there, and g(u) 6 1,
Z 1/2


exp euT + auT + e(1−u)T + a(1 − u)T + T g(u) du
ψ(T ) 6 2
0

62

Z

1/2
0



exp euT + eT −uT + aT + T du.

(6.3)

We consider two cases.
(i) If uT 6 1, then e−uT 6 1 − 21 uT , and thus
euT + eT −uT + aT + T 6 e + eT (1 − 21 uT ) + (a + 1)T.

(6.4)

Hence, the contribution to (6.3) for u 6 1/T is no more than
Z 1/T


exp eT + (a + 1)T + e − 21 T eT u du
2
0


 1
< 2 exp eT + (a + 1)T + e 1 T
2T e
e

4e
=
exp eT + aT 6 0.7ψ(T ),
T
.
by (6.2) and T > t2 = 100, since 4ee = 60.62.
(ii) For uT > 1 and u < 12 , recalling T > t2 = 100,

(6.5)

euT + eT −uT + aT + T 6 2eT −uT + aT + T 6 2e−1 eT + aT + T
6 0.8eT + T + aT 6 0.9eT + aT
= eT + aT − 0.1eT 6 eT + aT − 100.

(6.6)

Hence, the contribution to (6.3) for uT > 1 is less than, recalling (6.2),

exp eT + aT − 100 = e−100 ψ(T ) < 0.1ψ(T ).
(6.7)
Using (6.5) and (6.7) in (6.3), we find

ψ(T ) < 0.7ψ(T ) + 0.1ψ(T ),

(6.8)

a contradiction. Hence T cannot exist and (6.1) holds for all t > 0.



Proof of upper bound in (1.11). For x > 0 and any t > 0, by Lemma 6.1,

P(Z > x) 6 e−tx E etZ = e−tx ψ(t) 6 exp −tx + et + at .
(6.9)

We take t = ln x (assuming x > 1) and obtain


P(Z > x) 6 exp −x ln x + x + O(ln x) ,

x > 1.

(6.10)

(The optimal choice of t is actually ln(x−a), but this leads to the same result
up to o(1) in the exponent, which is absorbed by the error term O(ln x).) 
Acknowledgement. I thank David Belius and Jim Fill for helpful comments.

8

SVANTE JANSON

References
[1] Michael Drmota, Random Trees. Springer, Vienna, 2009.
[2] James Allen Fill and Svante Janson, Smoothness and decay properties
of the limiting Quicksort density function. Mathematics and Computer
Science (Proceedings, Colloquium on Mathematics and Computer Science, Versailles 2000), eds. D. Gardy and A. Mokkadem, Birkhäuser,
Basel, 2000,
[3] James Allen Fill and Svante Janson, A characterization of the set of
fixed points of the Quicksort transformation. Electronic Comm. Probab.
5 (2000), no. 9, 77–84.
[4] James Allen Fill and Svante Janson, Approximating the limiting Quicksort distribution. Random Structures Algorithms 19 (2001), no. 3-4,
376–406.
[5] James Allen Fill and Svante Janson, Quicksort asymptotics. J. Algorithms 44 (2002), no. 1, 4–28.
[6] Charles Knessl and Wojciech Szpankowski, Quicksort algorithm again
revisited. Discrete Math. Theor. Comput. Sci. 3 (1999), 43–64.
[7] Donald E. Knuth, The Art of Computer Programming. Vol. 3: Sorting
and Searching. 2nd ed., Addison-Wesley, Reading, Mass., 1998.
[8] C. J. H. McDiarmid and R. B. Hayward, Large deviations for Quicksort.
J. Algorithms 21 (1996), no. 3, 476–507.
[9] Mireille Régnier, A limiting distribution for quicksort. RAIRO Inform.
Théor. Appl. 23 (1989), no. 3, 335–343.
[10] Uwe Rösler, A limit theorem for “Quicksort”. RAIRO Inform. Théor.
Appl. 25 (1991), no. 1, 85–100.
[11] Kok Hooi Tan and Petros Hadjicostas, Some properties of a limiting
distribution in Quicksort. Statist. Probab. Lett. 25 (1995), 87–94.
Department of Mathematics, Uppsala University, PO Box 480, SE-751 06
Uppsala, Sweden
E-mail address: svante.janson@math.uu.se
URL: http://www2.math.uu.se/∼svante/

