COMPARISONS IN HOARE’S FIND ALGORITHM

PETER KIRSCHENHOFER AND HELMUT PRODINGER

Abstract. We study the number of comparisons in Hoare’s Find algorithm. Using trivariate generating functions, we get an explicit expression for the variance of the number of comparisons, if we search for the jth element in a random permutation of n elements. The variance is also asymptotically evaluated under the assumption that j is proportional to n. Similar results for the number of passes (recursive calls) are given, too.

1. Introduction

The traditional sorting method Quicksort [11, 6] uses a pivot element and a partitioning strategy in order to bring the pivot element into its correct position and having only smaller elements to the left and larger elements to the right, so that the procedure can be applied recursively to the smaller subfiles. There is a relation between Quicksort and binary search trees, as can be seen in the example in Figure 1. Subfiles are indicated by rectangular boxes, and the leftmost element will be the pivot element.

The corresponding binary search tree is depicted in Figure 2.

If one only wants the find the jth ranked element (which is j, since we assume that the elements in question are {1, 2, …, n}), one uses the same partitioning strategy, but follows only the path which contains the sought element. This is the same as to say that one goes down recursively in only one subfile. This procedure is called Hoare’s Find algorithm [5].

There is some renewed interest in Hoare’s find algorithm, as can be seen from the following references, [12, 14, 8, 15]. For some general background on binary search trees we cite [13]; see also [7].

Knuth [10] has already computed the average number of comparisons C_{n,j}. For this, it is assumed that every permutation of {1, 2, …, n} is equally likely, and that the partitioning phase needs n − 1 comparisons. Then there is the recursion

C_{n,j} = n − 1 + \frac{1}{n} ∑_{1≤k<j} C_{n−k,j−k} + \frac{1}{n} ∑_{j<k≤n} C_{k−1,j} .  (1)

The solution is

C_{n,j} = 2(n + 3 + (n + 1)H_{n} − (j + 2)H_{j} − (n + 3 − j)H_{n+1−j}) .  (2)

Here, H_{n} = ∑_{1≤k≤n} \frac{1}{k} is the nth harmonic number; we will also need harmonic numbers of order two, H_{n}^{(2)} = ∑_{1≤k≤n} \frac{1}{k^{2}} .

More generally, one can also set up an analogous recursion for the probability generating functions, viz.

C_{n,j}(v) = \frac{v^{n−1}}{n} [ ∑_{1≤k<j} C_{n−k,j−k}(v) + 1 + ∑_{j<k≤n} C_{k−1,j}(v)] .  (3)

Date: April 28, 1996.

[figure: 1; 1; 1; 1; 2; 2; 2; 2; 2; 1; 3; 4; 5; 9; 9; 4; 3; 6; 6; 6; 5; 5; 7; 7; 7; 6; 7; 3; 3; 3; 7; 8; 8; 8; 8; 8; 6; 4; 4; 4; 9; 9; 9; 5; 5; 10; 10; 10; 10; 10]

Figure 1. The partition process

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

Figure 2. The corresponding binary search tree with 10 nodes

In this paper we want to compute the variance of the number of comparisons.

This requires an incredible amount of computations (by Maple, with careful human guidance). We cannot present all the details, but rather present the cornerstones of the whole procedure. We have to deal a lot with harmonic numbers, and use many identities about them which can be found e.g. in [9, 3, 4].

2. Analysis

Following a suggestion of Philippe Flajolet, we rather think about binary search trees (as explained above) and use a trivariate generating function.

The coefficient of z^{n}u^{j}v^{m} in F (z; u, v) is the probability that it takes m comparisons to find node j, under the usual assumption that all permutations of n elements are equally likely. For example, the tree in Figure 2 (obtained by the permutation in Figure 1) contributes

\frac{z^{10}}{10!} (u^{1}v^{9} + u^{2}v^{9} + u^{3}v^{22} + u^{4}v^{22} + u^{5}v^{21} + u^{6}v^{23} + u^{7}v^{23} + u^{8}v^{23} + u^{9}v^{16} + u^{10}v^{16}) .(4)

Recursion (3) translates into the fundamental equation

\frac{∂}{∂z} F (z; u, v) = \frac{F (zv; u, v)}{1 − zv} + \frac{u}{(1 − zv)(1 − zuv)} + \frac{u F (zv; u, v)}{1 − zuv} .  (5)

We can see this by multiplying the recursion (3) by nz^{n−1}u^{j} and summing over n and j. However, with a little experience, one can deduce it directly from the underlying binary search trees.

When speaking of differential equations, we will assume that z is the variable, whereas u and v are parameters.

Note the special value

F (z; u, 1) = \frac{zu}{(1 − z)(1 − zu)} = ∑_{1≤j≤n} u^{j}z^{n} .  (6)

If we derive the fundamental equation (5) w.r.t. v, and set v = 1, we get a differential equation for the generating function G(z, u) of the average values C_{n,j}, which Maple is able to solve^{1}, subject to the initial condition G(0, u) = 0. It is

\begin{aligned}G(z, u) & = \frac{2}{(1 − u)(1 − z)(1 − zu)}[(u − 2) log \frac{1}{1 − zu} + u(2u − 1) log \frac{1}{1 − z} ] \\ & + \frac{2zu(z^{2}u − 2zu + 3 − 2z)}{(1 − z)^{2}(1 − zu)^{2}} , \end{aligned}  (7)

which gives the coefficients C_{n,j}. (Knuth derived them using an elementary method.)

If we derive the fundamental equation (5) two times w.r.t. v, and set v = 1, and use the already computed function G(z, u), we get a differential equation for the generating function D(z, u) of the second factorial moments D_{n,j}. Its solution is

D(z, u) = \frac{4(2 − u)^{2}}{(1 − z)(1 − zu)(1 − u)^{2}} log^{2} \frac{1}{1 − zu}

+ \frac{4u(1 − 2u)^{2}}{(1 − z)(1 − zu)(1 − u)^{2}} log^{2} \frac{1}{1 − z}

− \frac{z^{2}u(−10z^{3}u^{2} − 5z^{2}u^{2} + 6zu^{2} − 15u − 5z^{2}u + 38zu − 15 + 6z)}{(1 − z)^{3}(1 − zu)^{3}} + → next page

(8)

1We cannot refrain from mentioning a peculiarity of Maple. It frequently replaces log(1 − z) by log(z − 1) + iπ &c. To avoid this unpleasant feature, we had to replace z by −z and u by −u.

+ \frac{8u(2 − u)(1 − 2u)}{(1 − z)(1 − zu)(1 − u)^{2}} log \frac{1}{1 − zu} log \frac{1}{1 − u}

+ \frac{8(2 − u)(1 − 2u)}{(1 − z)(1 − zu)(1 − u)^{2}} log \frac{1}{1 − z} log \frac{1}{1 − u}

+ \frac{8u(2 − u)(1 − 2u)}{(1 − z)(1 − zu)(1 − u)^{2}} log \frac{1}{1 − zu} log(−u)

− \frac{2u(−5z^{2}u + 19z^{2}u^{2} − 11zu^{2} − 10zu + z + 3u + 3)}{(1 − u)(1 − z)^{2}(1 − zu)^{2}} log \frac{1}{1 − z}

− \frac{10z^{2}u^{2} − 38z^{2}u − 2zu^{2} + 20zu + 22z − 6u − 6}{(1 − u)(1 − z)^{2}(1 − zu)^{2}} log \frac{1}{1 − zu}

− \frac{8u(2 − u)(1 − 2u)}{(1 − z)(1 − zu)(1 − u)^{2}} (dilog( − \frac{(1 − z)u}{1 − u}) − dilog( − \frac{u}{1 − u}))

− \frac{8(2 − u)(1 − 2u)}{(1 − z)(1 − zu)(1 − u)^{2}} (dilog(\frac{1 − zu}{1 − u}) − dilog(\frac{1}{1 − u})) .

Let us recall the definition of the dilogarithm [1],

dilog z = ∫_{1}^{z} \frac{log t}{1 − t} dt .  (9)

The appearence of a term log(−u) looks strange at first sight, but it compensates with the dilog–terms.

In order to get the coefficients, we rewrite D(z, u) as follows (with the heavy use of Maple),

D(z, u) = \frac{9}{(1 − z)^{3}} ∑_{j≥1} u^{j}

+ log^{2} \frac{1}{1 − z} ∑_{j≥1} u^{j}\{\frac{4(j − 4)}{(1 − z)^{2}} + \frac{4(z^{j−3} − z)}{(1 − z)^{3}} + \frac{4z^{j−3}(−1 − 2z + z^{2})}{1 − z}\}

+ \frac{1}{(1 − z)^{2}} ∑_{j≥1} u^{j}\{ − 8(j + 2)H_{j} + 21j − 25\}

+ \frac{1}{(1 − z)^{2}} log \frac{1}{1 − z} ∑_{j≥2} u^{j}\{(8j − 16H_{j−1} − 26)z^{j}

+ ( − 16j + 70 + 24H_{j−1} − \frac{8}{j − 1})z^{j−1}

+ ∑_{i=2}^{j−1} (8H_{j−i} − \frac{8i}{j − i} + 16 − \frac{16}{i + 1} + \frac{40}{i} − \frac{16}{i − 1})z^{j−i}

+ ( − 8H_{j} + \frac{24}{j} − 12 − \frac{16}{j − 1})\}

+ \frac{1}{(1 − z)^{2}} log \frac{1}{1 − z} · u(10 − 18z) + → next page

(10)

+ \frac{1}{1 − z} ∑_{j≥1} u^{j}\{(2j^{2} + 18j + 16)H_{j}^{2} + ( − 6j^{2} − 14j + 14 − \frac{16}{j})H_{j}

− (2j^{2} + 10j + 16)H_{j}^{(2)} − 2j^{2} + 25j + 10} .

The most complicated term in this expansion is the \frac{1}{1−z} term

8\frac{(2 − u)(1 − 2u)}{(1 − u)^{2}} dilog \frac{1}{1 − u} + 4\frac{(2 − u)^{2}}{(1 − u)^{3}} log^{2} \frac{1}{1 − u}

+2\frac{11 − u}{(1 − u)^{2}} log \frac{1}{1 − u} + \frac{u(13 − 41u + 10u^{2})}{(1 − u)^{3}} .

(11)

Reading of the coefficient of u^{j} is pretty much standard except for the following

[u^{j}]8\frac{(2 − u)(1 − 2u)}{(1 − u)^{2}} dilog \frac{1}{1 − u} = 4jH_{j}^{2} − 8\frac{j^{2} + j + 2}{j}H_{j} + 4jH_{j}^{(2)} + 8j .  (12)

For this one we argue as follows. Since

\frac{d}{du} dilog \frac{1}{1 − u} = (−\frac{1}{1 − u} − \frac{1}{u}) log \frac{1}{1 − u} ,  (13)

we find

[u^{j}] dilog \frac{1}{1 − u} = −\frac{1}{j} (H_{j−1} + \frac{1}{j})  (14)

The convolution, caused by the factor \frac{1}{(1−u)^{2}} , is then handled by formulæ in [9].

Now we read of the coefficient of u^{j}z^{n} in D(z, u), as shown in (10). Using all kind of identities for harmonic numbers (see [9]) we get as an intermediary result

D_{n,j} = −2(n + 1)(n + 8 − 2j)H_{n}^{2} − 8(n + 1) H_{n} H_{j}

+ \frac{(4 − 32n − 12n^{2})j^{2} + (44n^{2} + 12n^{3} + 28n − 4)j + 16n + 16}{j(n + 1 − j)} H_{n}

+ 2(j + 8)(j + 1) H_{j}^{2}

+ ( − 4j^{2} + (12 + 8n)j − 4n^{2} + 8 − 12n) H_{j}H_{n+1−j}

− 2\frac{(−6n − 14)j^{3} + (14n + 17 + 6n^{2})j^{2} + (−3 + 6n^{2} + 3n)j + 8n + 8}{j(n + 1 − j)} H_{j}

+ (2j^{2} + (−4n − 18)j + 2n^{2} + 18n + 32) H_{n+1−j}^{2}

− 2\frac{(6n + 14)j^{3} + (−12n^{2} − 25 − 46n)j^{2} + (37n + 11 + 32n^{2} + 6n^{3})j + 8n + 8}{j(n + 1 − j)} H_{n+1−j}

+ 2(n + 1)(n + 8 − 2j) H_{n}^{(2)} − (2j^{2} + 16 + 10j) H_{j}^{(2)}

+ ( − 2n^{2} + 4nj − 18n − 2j^{2} − 32 + 18j) H_{n+1−j}^{(2)} + → next page (15)

+ \frac{10j^{4} + (−20n − 20)j^{3} + (n^{2} − 66 − 13n)j^{2} + (76 + 9n^{3} + 42n^{2} + 101n)j + 32}{2j(n + 1 − j)}

+ 4(n + 2 − 2j)(n + 1) ∑_{k=1}^{j} \frac{H_{n−k}}{k} + 8(n + 1 − j) ∑_{k=1}^{j} \frac{H_{n+k−j}}{k} .

In this representation, there appear two sums, which (most likely) cannot be simplified any further. Also, from this representation, the symmetry D_{n,j} = D_{n,n+1−j} is not at all obvious. Therefore we derived the following lemmata. Lemma 1. [Reciprocity law]

∑_{k=1}^{j} \frac{H_{n−k}}{k} + ∑_{k=1}^{n+1−j} \frac{H_{n−k}}{k} = H_{j}H_{n+1−j} + H_{n}^{2} − H_{n}^{(2)} − \frac{1}{j(n + 1 − j)}  (16)

Lemma 2. [Reciprocity law]

\begin{aligned}∑_{k=1}^{j} \frac{H_{n+k−j}}{k} + ∑_{k=1}^{n+1−j} \frac{H_{j+k−1}}{k} & = \frac{1}{2}(H_{j}^{2} + H_{j}^{(2)}) + \frac{1}{2}(H_{n+1−j}^{2} + H_{n+1−j}^{(2)}) \\ & + H_{j}H_{n+1−j} + \frac{1}{j(n + 1 − j)} \\ & + \frac{n + 1}{j(n + 1 − j)}(H_{n} − H_{j} − H_{n+1−j}) . \end{aligned}  (17)

And here is the formula relating the two types of sums. Lemma 3.

\begin{aligned}∑_{k=1}^{j} \frac{H_{n−k}}{k} + ∑_{k=1}^{j} \frac{H_{n+k−j}}{k} & = \frac{1}{n + 1 − j} (H_{n} − H_{j} − H_{n+1−j}) + H_{j}H_{n} + H_{j}H_{n+1−j} \\ & − H_{n}H_{n+1−j} + \frac{1}{2}(H_{n}^{2} − H_{n}^{(2)}) + \frac{1}{2}(H_{n+1−j}^{2} + H_{n+1−j}^{(2)}) \end{aligned} (18)

All three lemmata can be easily proved by setting up bivariate generating functions on both sides. The formulæ are ‘nice’ and easier to prove than to find. As an example, we give the proof of Lemma 1. In terms of generating functions we have to prove that

\frac{1}{(1 − u)(1 − z)} log \frac{1}{1 − uz} log \frac{1}{1 − z} − \frac{u}{(1 − u)(1 − uz)} log^{2} \frac{1}{1 − uz}

+ \frac{u}{(1 − 1/u)(1 − uz)} log \frac{1}{1 − z} log \frac{1}{1 − uz} − \frac{1}{(1 − 1/u)(1 − z)} log^{2} \frac{1}{1 − z}

= \frac{1}{z(1 − uz)(1 − z)} log \frac{1}{1 − uz} log \frac{1}{1 − z} + \frac{u}{(1 − u)(1 − z)} log^{2} \frac{1}{1 − z}

− \frac{u}{(1 − u)(1 − uz)} log^{2} \frac{1}{1 − uz} − \frac{1}{z} log \frac{1}{1 − z} log \frac{1}{1 − uz} ,

(19)

which is easily seen to be true.

Using the lemmata, we can do the following,

\begin{aligned}(n + 1 − 2j) ∑_{k=1}^{j} \frac{H_{n−k}}{k} & = (n + 1 − j) ∑_{k=1}^{j} \frac{H_{n−k}}{k} + j ∑_{k=1}^{n+1−j} \frac{H_{n−k}}{k} \\ & − j(H_{j}H_{n+1−j} + H_{n}^{2} − H_{n}^{(2)} − \frac{1}{j(n + 1 − j)}) . \end{aligned}  (20)

This gives us the final result on the second factorial moments. Proposition 1.

\begin{aligned}D_{n,j} & = −2(n + 1)(n + 6) H_{n}^{2} \\ & − 8H_{n}(jH_{j} + (n + 1 − j) H_{n+1−j}) \\ & + 4\frac{−(3n^{2} + 8n + 1)j^{2} + (n + 1)(3n^{2} + 8n + 1)j + 4(n + 1)}{j(n + 1 − j)} H_{n} \\ & + 2(j + 8)(j + 1)H_{j}^{2} + 2(n + 9 − j)(n + 2 − j) H_{n+1−j}^{2} \\ & + 4( − j^{2} + (n + 1)j − n^{2} − n + 4)H_{j} H_{n+1−j} \\ & − \frac{2}{j(n + 1 − j)}( − 2(3n + 7)j^{3} + (6n^{2} + 14n + 13)j^{2} + (n + 1)(6n + 1)j + 8(n + 1)) H_{j} \\ & − \frac{2}{j(n + 1 − j)}(2(3n + 7)j^{3} − (12n^{2} + 46n + 29)j^{2} \\ & + (n + 1)(6n^{2} + 26n + 15)j + 8(n + 1)) H_{n+1−j} \\ & + 2(n + 1)(n + 6)\} H_{n}^{(2)} \\ & − 2(j^{2} + 5j + 8) H_{j}^{(2)} − 2(j^{2} − (2n + 7)j + n^{2} + 7n + 14) H_{n+1−j}^{(2)} \\ & + \frac{10j^{4} − 20(n + 1)j^{3} + (n^{2} − 13n − 66)j^{2} + (9n^{2} + 33n + 76)(n + 1)j + 32}{2j(n + 1 − j)} \\ & + 4n((n + 1 − j) ∑_{k=1}^{j} \frac{H_{n−k}}{k} + j ∑_{k=1}^{n+1−j} \frac{H_{n−k}}{k} ) . \end{aligned} (21)

Computing Var_{n,j} = D_{n,j} + C_{n,j} − (C_{n,j})^{2}, we find the variance. Theorem 1. The variance of the number of comparisons needed to find the jth element out of n elements is given by the exact formula

Var_{n,j} = −2(n + 1)(3n + 8) H_{n}^{2}

+ 8 H_{n} H_{j}(n(j + 2) + 2) + 8 H_{n} H_{n+1−j}(n(n + 3 − j) + 2)

+ 2\frac{−(2n^{2} + n − 9)j^{2} + (n + 1)(2n^{2} + n − 9)j + 8(n + 1)}{j(n + 1 − j)} H_{n}

− 2j(j − 1) H_{j}^{2} − 2(n + 1 − j)(n − j) H_{n+1−j}^{2}

+ 4(j^{2} − (n + 1)j − n^{2} − 5n − 8) H_{j} H_{n+1−j} + → next page (22)

− \frac{2}{j(n + 1 − j)}( − (2n + 3)j^{3} + (2n^{2} + 7n + 24)j^{2} − (n + 1)(2n + 21)j + 8(n + 1)) H_{j}

− \frac{2}{j(n + 1 − j)}((2n + 3)j^{3} − (4n^{2} + 8n − 15)j^{2}

+ (n + 1)(2n^{2} + 3n − 18)j + 8(n + 1)) H_{n+1−j}

+ 2(n + 1)(n + 6) H_{n}^{(2)}

− 2(j^{2} + 5j + 8) H_{j}^{(2)} − 2(j^{2} − (2n + 7)j + n^{2} + 7n + 14) H_{n+1−j}^{(2)}

+ \frac{10j^{4} − 20(n + 1)j^{3} + (9n^{2} + 31n − 6)j^{2} + (n^{2} − 11n + 16)(n + 1)j + 32}{2j(n + 1 − j)}

+ 4n((n + 1 − j) ∑_{k=1}^{j} \frac{H_{n−k}}{k} + j ∑_{k=1}^{n+1−j} \frac{H_{n−k}}{k} ) .

In the instance n = 2N + 1, j = N + 1 (searching for the median), we can use the first reciprocity law to simplify the variance. We get

\begin{aligned}Var_{2N+1,N+1} & = −8(2N + 5)(N + 1)H_{2N+1}^{2} + 16(2N + 5)(N + 1)H_{2N+1}H_{N+1} \\ & + 4\frac{4N^{3} + 9N^{2} + 2N + 5}{N + 1}H_{2N+1} − 8(2N^{2} + 7N + 7)H_{N+1}^{2} \\ & − 4\frac{4N^{3} + 9N^{2} − 13N − 2}{N + 1}H_{N+1} + 24(N + 1)H_{2N+1}^{(2)} \\ & − 4(N^{2} + 7N + 14)H_{N+1}^{(2)} + \frac{7N^{4} + 15N^{3} + 9N^{2} + 5N + 20}{(N + 1)^{2}} . \end{aligned} (23)

Asymptotically we get from this

Var_{2N+1,N+1} ∼ N^{2}(16 log 2 − 16 log^{2} 2 − \frac{2}{3}π^{2} + 7) .  (24)

The numerical constant is 3.823370396 .

To get a better feeling about the sums ∑_{k=1}^{j} \frac{H_{n−k}}{k}, we compute their average

\frac{1}{n} ∑_{1≤j≤n} ∑_{k=1}^{j} \frac{H_{n−k}}{k} = \frac{n + 1}{n} (H_{n}^{2} − H_{n}^{(2)}) − H_{n} + 1 .  (25)

It might be even more instructive to compute the average value

\begin{aligned}\frac{1}{n} ∑_{1≤j≤n} & [(n + 1 − j) ∑_{k=1}^{j} \frac{H_{n−k}}{k} + j ∑_{k=1}^{n+1−j} \frac{H_{n−k}}{k} ] \\ & = \frac{(n + 2)(n + 1)}{n} (H_{n}^{2} − H_{n}^{(2)}) − \frac{3n + 5}{2} H_{n} + \frac{5n + 11}{4} . \end{aligned}  (26)

Now we want to study the asymptotic behaviour of the variance, if n → ∞ and j = ρn, 0 < ρ < 1.

Using the well known asymptotics for the harmonic numbers and Euler’s summation formula, we find the asymptotic behaviour of the extra sum.

Lemma 4. As n → ∞ and j = ρn with 0 < ρ < 1, we have

∑_{k=1}^{j} \frac{H_{n−k}}{k} = log^{2} n + (2γ + log ρ) log n + (γ^{2} + γ log ρ − dilog(1 − ρ)) + o(1) . (27)

Using this intermediary result in our formula for the variance, an elementary calculation gives us the asymptotic evaluation of the variance. Theorem 2. The variance of the number of comparisons in Hoare’s Find algorithm to find the ρn–th out of n elements (0 < ρ < 1) fulfills for n → ∞

Var_{n,ρn} ∼ n^{2} ( − 2ρ^{2} log^{2} ρ + 4(ρ^{2} − ρ − 1) log ρ log(1 − ρ) − 2(1 − ρ)^{2} log^{2}(1 − ρ)

− 4ρ log ρ − 4(1 − ρ) log(1 − ρ) − 4ρ dilog ρ − 4(1 − ρ) dilog(1 − ρ)

+ \frac{2}{3}π^{2}ρ(1 − ρ) + 5ρ(1 − ρ) + \frac{1}{2}) . (28)

0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 0  0.2  0.4  0.6  0.8  1

Figure 3. The coefficient of n^{2} in Theorem 2, as a function of ρ

3. The number of passes

A similar but somewhat easier treatment is possible for the number of passes (recursive calls) instead of the number of comparisons. Therefore we only cite the results.

We have the fundamental equation

\frac{∂}{∂z} F (z; u, v) = \frac{v F (z; u, v)}{1 − z} + \frac{uv}{(1 − z)(1 − zu)} + \frac{uv F (z; u, v)}{1 − zu}  (29)

The equation can easily be gained from referring to (5): Observing the fact that this time the partitioning phase “costs” 1 (pass) yielding a factor v^{1} instead of a “cost” of n − 1 (comparisons) which corresponded to the substitution z → zv on the right-hand-side of (5) we find (29).

The expectation is an old result of Arora and Dent [2];

E_{n,j} = H_{j} + H_{n+1−j} − 1 .  (30)

For the variance we get

\begin{aligned}Var_{n,j} & = \frac{2(n + 1)}{j(n + 1 − j)} H_{n} + (1 − \frac{2(n + 1)}{j(n + 1 − j)}) (H_{j} + H_{n+1−j}) \\ & − (H_{j}^{(2)} + H_{n+1−j}^{(2)}) + \frac{2}{j(n + 1 − j)} + 2 . \end{aligned}  (31)

Acknowledgement. One of us (H. P.) had the opportunity to use the powerful computers at Inria. Thanks are due to P. Flajolet for the generous invitation.

References

[1] M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions. Dover, 1973. A reprint of the tenth National Bureau of Standards edition, 1964.

[2] S. Arora and W. Dent. Randomized binary search technique. Communications of the ACM, 12:77–80, 1969.

[3] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison Wesley, 1989.

[4] D. H. Greene and D. E. Knuth. Mathematics for the analysis of algorithms. Birkhauser, Boston, second edition, 1982.

[5] C. A. R. Hoare. Find (Algorithm 65). Communications of the ACM, 4:321–322, 1961.

[6] C. A. R. Hoare. Quicksort. Computer Journal, 5:10–15, 1962.

[7] H.-K. Hwang. On the average shape of binary search trees. Unpublished manuscript, 1990.

[8] P. Kirschenhofer, C. Martínez, and H. Prodinger. Analysis of Hoare’s Find algorithm with median–of– three partition. Submitted, 1995.

[9] D. E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms. Addison-Wesley, 1968. Second edition, 1973.

[10] D. E. Knuth. Mathematical analysis of algorithms. In Information Processing 71, pages 19–27. North Holland Publishing Company, 1972. Proceedings of IFIP Congress, Ljubljana, 1971.

[11] D. E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 1973.

[12] J. Lent and H. M. Mahmoud. Average–case analysis of multiple quickselect: An algorithm for finding order statistics. Statistics and Probability Letters (to appear).

[13] H. M. Mahmoud. Evolution of Random Search Trees. John Wiley, New York, 1992.

[14] H. M. Mahmoud, R. M. Modarres, and R. T. Smythe. Analysis of one-sided quicksort: An algorithm for order statistics. RAIRO, Theoretical Informatics and Applications, 29:255–276, 1995.

[15] H. Prodinger. Multiple quickselect — Hoare’s find algorithm for several elements. Information Processing Letters, 56:123–129, 1995.

Institut für Algebra und Diskrete Mathematik, Technical University of Vienna, Wiedner Hauptstrasse 8–10, A-1040 Vienna, Austria.

E-mail address: Peter.Kirschenhofer@tuwien.ac.at and Helmut.Prodinger@tuwien.ac.at