BINARY SEARCH TREE RECURSIONS WITH HARMONIC TOLL FUNCTIONS

ALOIS PANHOLZER^{†} AND HELMUT PRODINGER^{‡}

Abstract. We study recursions that are traditional in the context of binary search trees and quicksort with the (non–standard) toll function H_{n}.

When an explicit formula can be found there is nothing to beat it. In the rush to abstraction and generalization we often forget this.

Richard Askey

1. Introduction

Recursions like

a_{n} = t_{n} + \frac{1}{n} ∑_{k=0}^{n−1}(a_{k} + a_{n−1−k}), n ≥ 1, a_{0} = 1

with t_{n} = 1 or t_{n} = n are very common in analysis of algorithms and data structures, especially in the context of binary search trees and quicksort, see [9]. The extra quantities t_{n} are usually called the toll function.

In the recent paper [2] however, quantities t_{n} that have a logarithmic behaviour, occur. (The paper [1] also studies logarithmic costs, but the results are disjoint from ours.) To be more specific, a typical recursion from [2] is

T_{n} = 1 + S_{n} + \frac{1}{n} ∑_{k=0}^{n−1}(T_{k} + T_{n−1−k}),

where the quantities S_{n} are themselves solutions of divide–and–conquer recursions, and turn out to have logarithmic behaviour.

Although such recursions might look exotic at a first glance, they really are not, and appear naturally when e. g. a (recursive) divide–and–conquer strategy has extra costs at each level of recursion which are again given by a (different) recursion. Therefore, the recursions of interest occur typically when one recursive algorithm calls another (usually simpler) recursive algorithm.

Thus, in this paper, we undertake a thorough study of such recursions, where we consider instead of t_{n} = log n quantities like t_{n} = H_{n}, with harmonic numbers H_{n} = ∑_{1≤k≤n} \frac{1}{k}, which are much more manageable and represent the discrete analogue of the logarithm.

We refrain from investigating more exotic toll functions like \frac{n}{\sqrt{H_{n}}}, since they are not likely to occur as costs of (auxiliary) algorithms, used as subroutines in recursive algorithms, and since the class of toll functions that we consider is a reasonably large one where one can still hope for closed form solutions.

Date: January 18, 20001.

This paper can be seen both as a tuturial, showing the interested reader methods to attack such recursions, but also as a catalogue of solutions, as explained e. g. in [3]: Since solutions are linear, with a suitably large collection of basic solutions one can get ones own solution by constructing an appropriate linear combination.

A good way of imagining what we are doing is by thinking of binary search trees, where each node is weighted by a harmonic number, indexed by the size of the subtree having the particular node as a root. The basic parameter of interest is then the total weight of a binary search tree. (The sum of the weights of all nodes in the binary search tree.)

2. Total weight of a binary search tree

Let f_{n}(v) be the probability generating function of the parameter “total weight of a binary search tree,” i. e. [v^{k}]f_{n}(v) is the probability that a random binary search tree of size n has weight k. Observe carefully that this is not a polynomial, as the exponents will be in general some rational numbers. That is, however, not a major drawback, although it is harder to set up multivariate generating functions. In this section we are interested in the average a_{n} = f′_{n}(1) and variance b_{n} + a_{n} − a_{n}^{2}, with b_{n} = f′′_{n}(1).

Up to a certain level of complexity, one can resort to elementary methods, as we will demonstrate here. In later sections, however, the appropriate methodology is to work with differential equations.

The recursion

f_{n}(v) = v^{H_{n}} \frac{1}{n} ∑_{k=0}^{n−1} f_{k}(v)f_{n−1−k}(v), n ≥ 1, f_{0}(v) = 1

is quite straightforward; compare [9] for very similar recursions.

From that we find the prototype of a binary search tree recursion with a harmonic toll function, viz.

a_{n} = H_{n} + \frac{2}{n} ∑_{k=0}^{n−1} a_{k}, n ≥ 1, a_{0} = 0.

One can find the solution a_{n} = 2n−H_{n} for instance by inspection, which is not really a method but works well in practice when everything is sufficiently simple. Typically, a routine proof by induction would justify the answer. Now set b_{n} = f′′_{n}(1), then

b_{n} = H_{n}(H_{n} − 1) + 2H_{n}(a_{n} − H_{n}) + \frac{2}{n} ∑_{k=0}^{n−1} b_{k} + \frac{2}{n} ∑_{k=0}^{n−1} a_{k}a_{n−1−k}, n ≥ 1, b_{0} = 0.

Plugging in the known values and simplifying (we spare the reader with the simple but boring details) we find

nb_{n} − (n + 1)b_{n−1} = 4n^{2} − H_{n}^{2} − 3H_{n} + \frac{2}{n}H_{n} − 2H_{n}^{(2)} + \frac{1}{n^{2}} − 1,

where also harmonic numbers of the second order occur. The technique is explained in many textbooks on analysis of algorithms, e. g. [9]. The first step is to multiply by n, so that the difference of two such equations, once indexed by n and once by n − 1, makes the sum ∑_{k=0}^{n−1} b_{k} disappear.

The recursion may be rewritten as

\frac{b_{n}}{n + 1} − \frac{b_{n−1}}{n} = 4 − \frac{4}{n + 1} − \frac{H_{n}^{2}}{n} + \frac{H_{n+1}^{2}}{n + 1} − \frac{2H_{n+1}}{(n + 1)^{2}} + \frac{2H_{n}}{n^{2}} − \frac{5H_{n}}{n} + \frac{5H_{n+1}}{n + 1}

− \frac{5}{(n + 1)^{2}} − \frac{2H_{n}^{(2)}}{n} + \frac{2H_{n+1}^{(2)}}{n + 1} − \frac{1}{(n + 1)^{3}} + \frac{1}{n^{3}} − \frac{1}{n^{2}} ,

which can now be summed (a telescoping sum), with the result

\frac{b_{n}}{n + 1} = 4n − 4H_{n} − \frac{4}{n + 1} + 4 + \frac{H_{n}^{2}}{n + 1} + 5\frac{H_{n}}{n + 1} − 6H_{n}^{(2)} + 2\frac{H_{n}^{(2)}}{n + 1},

or

b_{n} = 4n(n + 2) − (4n − 1)H_{n} + H_{n}^{2} − 2(3n + 2)H_{n}^{(2)}.

In the simplification process of these sums, the most important identity is

∑_{k=1}^{n} \binom{k}{m}H_{k} = \binom{n + 1}{m + 1}(H_{n+1} − \frac{1}{m + 1}),

which can be found in [5] and other textbooks.

Thus the variance turns out to be

b_{n} + a_{n} − a_{n}^{2} = 4n(n + 2) − (4n − 1)H_{n} + H_{n}^{2} − 2(3n + 2)H_{n}^{(2)}
+ 2n − H_{n} − 4n^{2} + 4nH_{n} − H_{n}^{2}
= 10n − 2(3n + 2)H_{n}^{(2)}.

Asymptotically, the variance is given by

(10 − π^{2})n = 0.130395596 · n.

3. Refined results a la quickselect (=Hoare’s Find algorithm)

Traditionally, one associates the numbers 1, 2, …, n with the nodes of the binary search tree by traversing it in inorder. This reflects also the intuition that smaller elements are to the left, and larger elements to the right of the root. If one uses the quicksort strategy only to find element j, then the recursion of interest is

P_{n,j}(v) = v^{∗} \frac{1}{n}[ ∑_{k=1}^{j−1} P_{n−k,j−k}(v) + 1 + ∑_{k=j+1}^{n} P_{k−1,j}(v)], P_{1,1}(v) = v,

where ∗ stands for 1 in the instance “number of passes,” and for n − 1 in the instance “number of comparisons.” See for instance [4] and the references therein.

In the context of our study of harmonic recursions, it is thus naturally to introduce the probability generating functions

P_{n,j}(v) = v^{H_{n}} \frac{1}{n}[ ∑_{k=1}^{j−1} P_{n−k,j−k}(v) + 1 + ∑_{k=j+1}^{n} P_{k−1,j}(v)], P_{1,1}(v) = v.

The coefficient of v^{k} in it is the probability that in a random binary search tree of size n the node j is connected to the root via the path r_{1}, r_{2}, …, r_{s} = j, and the sum of the weights of the nodes r_{1}, r_{2}, …, r_{s} is k.

The expectations are again given by a_{n,j} = P′_{n,j}(1), or

a_{n,j} = H_{n} + \frac{1}{n}[ ∑_{k=1}^{j−1} a_{n−k,j−k} + ∑_{k=j+1}^{n} a_{k−1,j}], a_{1,1} = 1.

Although even here is it possible to solve it by elementary means, it is the right time to introduce generating functions,

F (z, u) = ∑_{1≤j≤n} a_{n,j}z^{n}u^{j}.

In order to translate the recursion into a differential equation, one must first compute

∑_{1≤j≤n} nH_{n}z^{n−1}u^{j} = \frac{u}{1 − u}(S(z) − S(zu))

with

S(z) = (\frac{1}{1 − z} log (\frac{1}{1 − z} ))′ = \frac{1}{(1 − z)^{2}} log (\frac{1}{1 − z} ) + \frac{1}{(1 − z)^{2}} .

Hence we obtain the differential equation

\frac{∂}{∂z} F (z, u) = \frac{u}{1 − u}(S(z) − S(zu)) + (\frac{u}{1 − zu} + \frac{1}{1 − z} )F (z, u), F (0, u) = 0

which is well within the range of Maple, and we obtain

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

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

− \frac{2zu}{(1 − zu)(1 − z)}.

Reading off coefficients is a (tedious) routine operation, with the result

a_{n,j} = \frac{1}{2}H_{j}^{2} + \frac{1}{2}H_{n+1−j}^{2} − \frac{1}{2}H_{j}^{(2)} − \frac{1}{2}H_{n+1−j}^{(2)} − H_{n} + 2H_{j} + 2H_{n+1−j} − 2.

One should observe the symmetry of the results (obvious from the definition): for each term with j, there is also a corresponding term with n + 1 − j.

To gain some asymptotic information, it is customary in this context to set j = ρn, with a fixed ratio 0 < ρ < 1. Then a_{n,j} ∼ log^{2} n.

Observe also that

∑_{j=1}^{n} a_{n,j} = ∑_{j=1}^{n} (H_{j}^{2} − H_{j}^{(2)}) − nH_{n} + 4 ∑_{j=1}^{n} H_{j} − 2n
= (n + 1)(H_{n}^{2} − H_{n}^{(2)}) + 2n − 2nH_{n} − nH_{n} + 4(n + 1)H_{n} − 4n − 2n
= (n + 1)(H_{n}^{2} − H_{n}^{(2)}) + nH_{n} + 4H_{n} − 4n.

Now we turn to the second factorial moments, which are given by b_{n,j} = P′′_{n,j}(1). We get here the recurrence

b_{n,j} = H_{n}(H_{n} − 1) + 2\frac{H_{n}}{n} [∑_{k=1}^{j−1} a_{n−k,j−k} + ∑_{k=j+1}^{n} a_{k−1,j}] + \frac{1}{n} [∑_{k=1}^{j−1} b_{n−k,j−k} + ∑_{k=j+1}^{n} b_{k−1,j}] , b_{1,1} = 0,

which simplifies by the above recursion for the a_{n,j}’s to

b_{n,j} = −3H_{n}^{2} − 5H_{n} + H_{n}H_{j}^{2} + H_{n}H_{n+1−j}^{2} − H_{n}H_{j}^{(2)} − H_{n}H_{n+1−j}^{(2)} + 4H_{n}H_{j} + 4H_{n}H_{n+1−j}

+ \frac{1}{n} ∑_{k=1}^{j−1} b_{n−k,j−k} + \frac{1}{n} ∑_{k=j+1}^{n} b_{k−1,j}.

The solution can be obtained by the following considerations. The recurrence

nb_{n,j} = ∑_{k=1}^{j−1} b_{n−k,j−k} + ∑_{k=j+1}^{n} b_{k−1,j} + X_{n,j} ,

where X_{n,j} is an arbitrary toll function with ordinary generating function X(z, u), leads to the differential equation

\frac{∂}{∂z} F (z, u) − (\frac{1}{1 − z} + \frac{u}{1 − uz} ) F (z, u) = \frac{X(z, u)}{z} ,

which has the solution

F (z, u) = \frac{1}{(1 − z)(1 − uz)} ∫_{t=0}^{z} \frac{(1 − t)(1 − ut)}{t}X(t, u)dt .

(In this case, Maple cannot do that, since the integral is no longer expressible in elementary functions.)

Extracting coefficients gives after some manipulations

b_{n,j} = ∑_{k=1}^{j} ∑_{r=k}^{n−j+k} \frac{X_{r,k}}{r} − ∑_{k=1}^{j} ∑_{r=k+1}^{n−j+k} \frac{X_{r−1,k}}{r} − ∑_{k=2}^{j} ∑_{r=k}^{n−j+k} \frac{X_{r−1,k−1}}{r} + ∑_{k=2}^{j} ∑_{r=k+1}^{n−j+k} \frac{X_{r−2,k−1}}{r} .

In our case, the X_{n,j}’s are given by

X_{n,j} = −3nH_{n}^{2} − 5nH_{n} + nH_{n}H_{j}^{2} + nH_{n}H_{n+1−j}^{2}
− nH_{n}H_{j}^{(2)} − nH_{n}H_{n+1−j}^{(2)} + 4nH_{n}H_{j} + 4nH_{n}H_{n+1−j} .

The following observation is also of some interest: If two toll functions X_{n,j} resp. X̄_{n,j} are given by

X_{n,j} = C_{n}D_{j} and X̄_{n,j} = C_{n}D_{n+1−j} ,

then for b_{n,j} resp. b̄_{n,j} we have

b̄_{n,j} = b_{n,n+1−j} .

So the problem is reduced to double summations for the terms nH_{n}, nH_{n}^{2}, nH_{n}H_{j}, nH_{n}H_{j}^{(2)} and nH_{n}H_{j}^{2}. Because of cancellations that occur a simple rewriting of b_{n,j} is advantageous with respect to an easier manipulation of the terms involved:

b_{n,j} = ∑_{k=1}^{j} ∑_{r=k+1}^{n−j+k} \frac{1}{r}(X_{r,k} − X_{r−1,k}) − ∑_{k=2}^{j} ∑_{r=k+1}^{n−j+k} \frac{1}{r}(X_{r−1,k−1} − X_{r−2,k−1}) + ∑_{k=2}^{j} \frac{1}{r}(X_{k,k} − X_{k−1,k−1}) + X_{1,1}.

For all the terms noted above, we can substitute the inner sums by expressions involving harmonic numbers, and simplify the remaining sum using formulæ like

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

∑_{k=1}^{n} \frac{H_{k}^{(2)}}{k^{2}} = \frac{1}{2}(H_{n}^{(2)})^{2} + \frac{1}{2}H_{n}^{(4)} ,

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

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

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

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

Eventually we find

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

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

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

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

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

+ \frac{1}{3}H_{j}^{3} − 5H_{j}H_{j}^{(2)} − \frac{1}{3}H_{j}^{(3)} − \frac{9}{2}H_{j}^{2} + \frac{12j + 9}{2}H_{j}^{(2)} + 2H_{j}^{(4)} − 22H_{j} + 4H_{j}H_{j}^{(3)}

+ \frac{1}{3}H_{n−j+1}^{3} − 5H_{n−j+1}H_{n−j+1}^{(2)} − \frac{1}{3}H_{n−j+1}^{(3)} − \frac{9}{2}H_{n−j+1}^{2} + \frac{12(n − j + 1) + 9}{2}H_{n−j+1}^{(2)}

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

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

+ 3H_{n}^{2} − 6(n + 1)H_{n}^{(2)} + 17H_{n} + 16.

To find an asymptotic equivalent for b_{n,j} for a fixed ratio j = ρn, with 0 < ρ < 1 and n → ∞ we can use the following relations, which can be obtained by using the asymptotic expansion H_{n−j+k} = log n + log(1 − ρ) + γ + log (1 + \frac{k}{(1−ρ)n}) + O (\frac{1}{n}) for 1 ≤ k ≤ j = ρn:

∑_{k=1}^{j} \frac{H_{k}H_{n−j+k}}{k} = \frac{1}{2} log^{3} n + O (log^{2} n) = ∑_{k=1}^{n−j+1} \frac{H_{k}H_{j−1+k}}{k} ,

∑_{k=1}^{j} \frac{H_{k}H_{n−j+k}^{2}}{k} = \frac{1}{2} log^{4} n + (log ρ + log(1 − ρ) + 2γ) log^{3} n + O (log^{2} n) = ∑_{k=1}^{n−j+1} \frac{H_{k}H_{j−1+k}^{2}}{k} ,

∑_{k=1}^{j} \frac{H_{n−j+k}^{2}}{k} = log^{3} n + O (log^{2} n) = ∑_{k=1}^{n−j+1} \frac{H_{j−1+k}^{2}}{k} .

The assumption that j = ρn with 0 < ρ < 1, is a usual one in the analysis of algorithms. (For instance in the study of hashing algorithms such a proportionality factor as ρ is called the load factor.) One particular aspect of such an assumption is that one has to consider only one parameter (n) which goes to infinity. Of course, such an assumption does not necessarily cover instances like n, j → ∞, as j ∼ log n.

The other terms involving sums are bounded by O (log^{2} n).

This leads to the asymptotic expansion for the second factorial moments b_{n,j},

b_{n,j} = log^{4} n + (2 log ρ + 2 log(1 − ρ) + 4γ + \frac{20}{3}) log^{3} n + O (log^{2} n) ,

for j = ρn with a fixed 0 < ρ < 1. As a consequence we find as the asymptotic equivalent of the variance b_{n,j} + a_{n,j} − a_{n,j}^{2} ∼ \frac{2}{3} log^{3} n.

4. Weight of subtrees

We consider now the total weight of subtrees in binary search trees. To do this, we introduce the probability generating function P_{n,j}(v) of the total weight of the subtree j in a binary search tree with n nodes. In other words, the coefficient [v^{k}]P_{n,j}(v) is the probability that the total weight of the subtree with root j is k, assuming that all permutations of n elements are equally likely. The average a_{n,j} is then obtained (as usual) as a_{n,j} = P′_{n,j}(1), and the variance as b_{n,j} + a_{n,j} − (a_{n,j})^{2}, with b_{n,j} = P′′_{n,j}(1).

We get the recurrence

P_{n,j}(v) = \frac{1}{n} (∑_{k=1}^{j−1} P_{n−k,j−k}(v) + ∑_{k=j+1}^{n} P_{k−1,j}(v) + v^{H_{n}}f_{j−1}(v)f_{n−j}(v)) , P_{1,1}(v) = v ,

where f_{n}(v) is the probability generating function of the total weight of a binary search tree, as introduced in section 2. This recursion is obtained by considering the three cases that the subtree with root j is in the right subtree or left subtree, or that it is the whole tree, in which case we must add a contribution of H_{n} to the total count.

For the expectations a_{n,j} = P′_{n,j}(1), we get the following recursion:

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

An approach with generating functions leads to the result

a_{n,j} = (n + 1)H_{n}^{(2)} − jH_{j}^{(2)} − (n + 1 − j)H_{n+1−j}^{(2)} + 2H_{j} + 2H_{n+1−j} + \frac{1}{j} + \frac{1}{n + 1 − j} − 5 ,

what means that the weight of the subtree j with j = ρn and 0 < ρ < 1 is asymptotically 4 log n.

5. A catalogue of solutions

In this section we give a list of solutions of

a_{n,j} = toll-function + \frac{1}{n}[ ∑_{k=1}^{j−1} a_{n−k,j−k} + ∑_{k=j+1}^{n} a_{k−1,j}], a_{1,1} = 1.

with various toll functions of the form n^{d}H_{n} and (simpler) n^{d}. We write j = n+1−j for convenience. (The solutions are obtained by an ansatz and matching coefficients.) Such a catalogue is especially useful for a repertoire approach, see [3].

For H_{n} we have

a_{n,j} = \frac{1}{2}(H_{j}^{2} − H_{j}^{(2)}) + \frac{1}{2}(H_{j}^{2} − H_{j}^{(2)}) + 2H_{j} + 2H_{j} − H_{n} − 2.

For nH_{n} we have

a_{n,j} = (n + 1)(H_{n}^{2} − H_{n}^{(2)}) − (\frac{3}{2} + j)(H_{j}^{2} − H_{j}^{(2)}) − (\frac{3}{2} + j)(H_{j}^{2} − H_{j}^{(2)})
+ (j − 4)H_{j} + (j − 4)H_{j} + (n + 4)H_{n} − n + 3.

For n^{2}H_{n} we have

a_{n,j} = −3(n + 1)(H_{n}^{2} − H_{n}^{(2)}) + (\frac{7}{2} + 3j)(H_{j}^{2} − H_{j}^{(2)}) + (\frac{7}{2} + 3j)(H_{j}^{2} − H_{j}^{(2)})
− (\frac{3}{2}j^{2} + \frac{7}{2}j − 8)H_{j} − (\frac{3}{2}j^{2} + \frac{7}{2}j − 8)H_{j} + (n + 2)(3n − 4)H_{n}
− \frac{7}{2}jj − \frac{1}{4}n^{2} + \frac{19}{4}n − 3.

For n^{3}H_{n} we have

a_{n,j} = 7(n + 1)(H_{n}^{2} − H_{n}^{(2)}) − (\frac{15}{2} + 7j)(H_{j}^{2} − H_{j}^{(2)}) − (\frac{15}{2} + 7j)(H_{j}^{2} − H_{j}^{(2)})
− (\frac{2}{3}j^{3} − 5j^{2} − \frac{26}{3}j + 16)H_{j} − (\frac{2}{3}j^{3} − 5j^{2} − \frac{26}{3}j + 16)H_{j} + (2n^{3} − 6n^{2} − 7n + 16)H_{n}
− (\frac{7}{6}n − \frac{61}{6})jj − \frac{1}{9}n^{3} + \frac{3}{2}n^{2} − \frac{205}{18}n + 3.

For n^{4}H_{n} we have

a_{n,j} = −15(n + 1)(H_{n}^{2} − H_{n}^{(2)}) + (\frac{31}{2} + 15j)(H_{j}^{2} − H_{j}^{(2)}) + (\frac{31}{2} + 15j)(H_{j}^{2} − H_{j}^{(2)})

− (\frac{5}{12}j^{4} − \frac{5}{2}j^{3} + \frac{145}{12}j^{2} + 19j − 32)H_{j} − (\frac{5}{12}j^{4} − \frac{5}{2}j^{3} + \frac{145}{12}j^{2} + 19j − 32)H_{j} + (\frac{5}{3}n^{4} − \frac{10}{3}n^{3} + \frac{40}{3}n^{2} + \frac{52}{3}n − 32)H_{n} + \frac{23}{72}j^{2}j^{2} − (\frac{23}{36}n^{2} − \frac{187}{72}n + \frac{214}{9})jj − \frac{1}{16}n^{4} + \frac{19}{24}n^{3} − \frac{51}{16}n^{2} + \frac{599}{24}n − 3.

For n^{5}H_{n} we have

a_{n,j} = 31(n + 1)(H_{n}^{2} − H_{n}^{(2)}) − (\frac{63}{2} + 31j)(H_{j}^{2} − H_{j}^{(2)}) − (\frac{63}{2} + 31j)(H_{j}^{2} − H_{j}^{(2)})

− (\frac{3}{10}j^{5} − \frac{7}{4}j^{4} + \frac{19}{3}j^{3} − \frac{105}{4}j^{2} − \frac{1189}{30}j − 64)H_{j} − (\frac{3}{10}j^{5} − \frac{7}{4}j^{4} + \frac{19}{3}j^{3} − \frac{105}{4}j^{2} − \frac{1189}{30}j − 64)H_{j} + (\frac{3}{2}n^{5} − \frac{5}{2}n^{4} + \frac{15}{2}n^{3} − \frac{55}{2}n^{2} − 38n + 64)H_{n} + (\frac{17}{40}n − \frac{13}{20})j^{2}j^{2} − (\frac{17}{40}n^{3} − \frac{7}{8}n^{2} + \frac{733}{120}n − \frac{3053}{60})jj − \frac{1}{25}n^{5} + \frac{41}{80}n^{4} − \frac{497}{360}n^{3} + \frac{559}{80}n^{2} − \frac{93743}{1800}n + 3.

For n^{6}H_{n} we have

a_{n,j} = −63(n + 1)(H_{n}^{2} − H_{n}^{(2)}) + (\frac{127}{2} + 63j)(H_{j}^{2} − H_{j}^{(2)}) + (\frac{127}{2} + 63j)(H_{j}^{2} − H_{j}^{(2)})

− (\frac{7}{30}j^{6} − \frac{7}{5}j^{5} + \frac{14}{3}j^{4} − 14j^{3} + \frac{273}{5}j^{2} + \frac{809}{10}j − 128)H_{j} − (\frac{7}{30}j^{6} − \frac{7}{5}j^{5} + \frac{14}{3}j^{4} − 14j^{3} + \frac{273}{5}j^{2} + \frac{809}{10}j − 128)H_{j} + (\frac{7}{5}n^{6} − \frac{21}{10}n^{5} + \frac{35}{6}n^{4} − \frac{91}{6}n^{3} + \frac{1673}{30}n^{2} + \frac{1189}{15}n − 128)H_{n} − \frac{47}{450}j^{3}j^{3} + (\frac{47}{100}n^{2} − \frac{301}{600}n + \frac{887}{600})j^{2}j^{2} − (\frac{47}{150}n^{4} − \frac{113}{600}n^{3} + \frac{491}{200}n^{2} − \frac{3839}{300}n + \frac{94553}{900})jj − \frac{1}{36}n^{6} + \frac{37}{100}n^{5} − \frac{241}{360}n^{4} + \frac{31}{10}n^{3} − \frac{5239}{360}n^{2} + \frac{2657}{25}n − 3.

For n^{7}H_{n} we have

a_{n,j} = 127(n + 1)(H_{n}^{2} − H_{n}^{(2)}) − (\frac{255}{2} + 127j)(H_{j}^{2} − H_{j}^{(2)}) − (\frac{255}{2} + 127j)(H_{j}^{2} − H_{j}^{(2)})

− (\frac{4}{21}j^{7} − \frac{6}{5}j^{6} + \frac{59}{15}j^{5} − \frac{21}{2}j^{4} + \frac{88}{3}j^{3} − \frac{1113}{10}j^{2} − \frac{5721}{35}j + 256)H_{j} − (\frac{4}{21}j^{7} − \frac{6}{5}j^{6} + \frac{59}{15}j^{5} − \frac{21}{2}j^{4} + \frac{88}{3}j^{3} − \frac{1113}{10}j^{2} − \frac{5721}{35}j + 256)H_{j} + (\frac{4}{3}n^{7} − \frac{28}{15}n^{6} + \frac{77}{15}n^{5} − \frac{35}{3}n^{4} + \frac{91}{3}n^{3} − \frac{1687}{15}n^{2} − \frac{809}{5}n + 256)H_{n} − (\frac{31}{126}n − \frac{347}{3150})j^{3}j^{3} + (\frac{31}{63}n^{3} − \frac{19}{150}n^{2} + \frac{1237}{900}n − \frac{9839}{3150})j^{2}j^{2} − (\frac{31}{126}n^{5} + \frac{509}{3150}n^{4} + \frac{129}{100}n^{3} − \frac{30697}{6300}n^{2} + \frac{164677}{6300}n − \frac{112079}{525})jj − \frac{1}{49}n^{7} + \frac{2}{7}n^{6} − \frac{54}{175}n^{5} + \frac{457}{280}n^{4} − \frac{389}{60}n^{3} + \frac{8283}{280}n^{2} − \frac{3155909}{14700}n + 3.

And here is the simpler set of solutions: For 1,

a_{n,j} = H_{j} + H_{j} − 1,

for n,

a_{n,j} = −(3j + 2)H_{j} − (3j + 2)H_{j} + 2(n + 1)H_{n} + 2n + 5

for n^{2},

a_{n,j} = (6j + 7)H_{j} + (6j + 7)H_{j} − 6(n + 1)H_{n} + \frac{3}{2}n^{2} − \frac{9}{2}n − 13 − \frac{9}{2}n + 3jj − 13

for n^{3},

a_{n,j} = −(14j + 15)H_{j} − (14j + 15)H_{j} + 14(n + 1)H_{n} + (2n − 8)jj + \frac{4}{3}n^{3} − 3n^{2} + \frac{29}{3}n + 29

for n^{4},

a_{n,j} = (30j + 31)H_{j} + (30j + 31)H_{j} − 30(n + 1)H_{n}
+ (\frac{5}{3}n^{2} − \frac{25}{6}n + \frac{55}{3})jj + \frac{5}{4}n^{4} − \frac{5}{2}n^{3} + \frac{25}{4}n^{2} − 20n − 61 − \frac{5}{6}j^{2}j^{2}

for n^{5},

a_{n,j} = −(62j + 63)H_{j} − (62j + 63)H_{j} + 62(n + 1)H_{n}

− (\frac{3}{2}n − 2)j^{2}j^{2} + (\frac{3}{2}n^{3} − \frac{5}{2}n^{2} + \frac{19}{2}n − 39)jj + \frac{6}{5}n^{5} − \frac{9}{4}n^{4} + \frac{31}{6}n^{3} − \frac{51}{4}n^{2} + \frac{1219}{30}n + 125

for n^{6},

a_{n,j} = (126j + 127)H_{j} + (126j + 127)H_{j} − 126(n + 1)H_{n}
+ \frac{7}{15}j^{3}j^{3} − (\frac{21}{10}n^{2} − \frac{14}{5}n + \frac{133}{30})j^{2}j^{2} + (\frac{7}{5}n^{4} − \frac{7}{5}n^{3} + \frac{91}{15}n^{2} − \frac{301}{15}n + \frac{1204}{15})jj
+ \frac{7}{6}n^{6} − \frac{21}{10}n^{5} + \frac{14}{3}n^{4} − \frac{21}{2}n^{3} + \frac{77}{3}n^{2} − \frac{819}{10}n − 253,

for n^{7},

a_{n,j} = −(254j + 255)H_{j} − (254j + 255)H_{j} + 254(n + 1)H_{n}
+ (\frac{4}{3}n − \frac{16}{15})j^{3}j^{3} − (\frac{8}{3}n^{3} − \frac{14}{5}n^{2} + \frac{91}{15}n − \frac{142}{15})j^{2}j^{2}
+ (\frac{4}{3}n^{5} − \frac{8}{15}n^{4} + \frac{21}{5}n^{3} − \frac{193}{15}n^{2} + \frac{613}{15}n − \frac{814}{5})jj
+ \frac{8}{7}n^{7} − 2n^{6} + \frac{22}{5}n^{5} − \frac{19}{2}n^{4} + 21n^{3} − \frac{103}{2}n^{2} + \frac{5756}{35}n + 509.

(Several general formulæ for the coefficients can be spotted from that.)

6. Results a la Multiple Quickselect

Several authors have considered Multiple Quickselect; see [6, 8, 7]. The idea is to use Quicksort (vs. Quickselect) to find a prescribed set of values, e. g. the third and the tenth; in general we search simultaneously for p elements with ranks j_{1}, j_{2}, …, j_{p} where 1 ≤ j_{1} < j_{2} < ⋯ < j_{p} ≤ n. Here we consider analogous recursions with harmonic toll functions:

X[n; j_{1}, …, j_{p}] = H_{n} + \frac{1}{n}( ∑_{t=1}^{p−1} ∑_{k=j_{t}+1}^{j_{t+1}} X[k − 1; j_{1}, …, j_{t}] + ∑_{k=j_{p}+1}^{n} X[k − 1; j_{1}, …, j_{p}]

+ ∑_{k=1}^{j_{1}−1} X[n − k; j_{1} − k, …, j_{p} − k] + ∑_{t=1}^{p−1} ∑_{k=j_{t}}^{j_{t+1}−1} X[n − k; j_{t+1} − k, …, j_{p} − k]) .

One finds that the solution of this recursion is given by

X[n; j_{1}, …, j_{p}] = \frac{1}{2}H_{j_{1}}^{2} − \frac{1}{2}H_{j_{1}}^{(2)} + 2H_{j_{1}} + \frac{1}{2}H_{n+1−j_{p}}^{2} − \frac{1}{2}H_{n+1−j_{p}}^{(2)} + 2H_{n+1−j_{p}}

+ ∑_{t=2}^{p} (H_{j_{t}+1−j_{t−1}}^{2} − H_{j_{t}+1−j_{t−1}}^{(2)} + 2H_{j_{t}+1−j_{t−1}}) − H_{n} − 2p .

The proof can be done by induction. The only formulæ which are required, are

∑_{k=1}^{n} H_{k}^{2} = (n + 1)H_{n}^{2} − (2n + 1)H_{n} + 2n ,  ∑_{k=1}^{n} H_{k}^{(2)} = (n + 1)H_{n}^{(2)} − H_{n} ,

∑_{k=1}^{n} H_{k} = (n + 1)H_{n} − n .

The proof is omitted here, because it is long, but completely routine. It should be remarked, that for the case p = 2 the recursion was solved by setting up generating functions and extracting coefficients of the solution of the resulting linear differential equation. The solution of the general case for arbitrary p was then guessed and verified by computer experiments.

7. Results a la Grand Averages

For the analysis of Multiple Quickselect, it was suggested that, instead of a given set of p values (see [8]) it is easier to consider all \binom{n}{p} subsets of size p. This leads to the Grand Averages of the number of passes and the number of comparisons. Here again we study such questions together with harmonic toll functions.

With the notation from the previous section, this means that we are interested in

X_{n,p} = \frac{1}{\binom{n}{p}} ∑_{1≤j_{1}<j_{2}<···<j_{p}≤n} X[n; j_{1}, …, j_{p}] .

To evaluate this, we use two summation formulæ, which can be found in [8]:

∑_{1≤j_{1}<j_{2}<···<j_{p}≤n} H_{j_{1}} = \binom{n + 1}{p}(H_{n+1} − H_{p}) = ∑_{1≤j_{1}<j_{2}<···<j_{p}≤n} H_{n+1−j_{p}} ,

∑_{t=2}^{p} ∑_{1≤j_{1}<j_{2}<···<j_{p}≤n} H_{j_{t}+1−j_{t−1}} = (p − 1)\binom{n + 2}{p}(H_{n+2} − H_{p}) − (p − 1)\binom{n}{p − 1} .

In a similar manner as shown there, one gets the remaining required formulæ:

∑_{1≤j_{1}<j_{2}<···<j_{p}≤n}(H_{j_{1}}^{2} − H_{j_{1}}^{(2)}) = \binom{n + 1}{p}((H_{n+1} − H_{p})^{2} − (H_{n+1}^{(2)} − H_{p}^{(2)}))

= ∑_{1≤j_{1}<j_{2}<···<j_{p}≤n}(H_{n+1−j_{p}}^{2} − H_{n+1−j_{p}}^{(2)}) ,

∑_{t=2}^{p} ∑_{1≤j_{1}<j_{2}<···<j_{p}≤n}(H_{j_{t}+1−j_{t−1}}^{2} − H_{j_{t}+1−j_{t−1}}^{2}) = (p − 1)\binom{n + 2}{p}((H_{n+2} − H_{p})^{2} − (H_{n+2}^{(2)} − H_{p}^{(2)})) .

Collecting all contributions and dividing by \binom{n}{p}, we get for the grand average:

X_{n,p} = \frac{p(n + 1)^{2}}{(n + 2 − p)(n + 1 − p)}((H_{n} − H_{p})^{2} − H_{n}^{(2)} + H_{p}^{(2)})

+ \frac{(1 + 2p)n^{2} + (1 + 8p)n + p(7 − p)}{(n + 2 − p)(n + 1 − p)}H_{n}

− \frac{2(n + 1)((p + 1)n + 2p + 1)}{(n + 2 − p)(n + 1 − p)}H_{p} − \frac{2p(n^{2} − pn − 2)}{(n + 2 − p)(n + 1 − p)}.

The formula for X_{n,p} can also be obtained more directly with generating functions. The starting point for this is the following recursion:

ψ_{n}(u, v) = v^{H_{n}} \frac{1 + u}{n} ∑_{j=0}^{n−1} ψ_{j}(u, v)ψ_{n−1−j}(u, v) + 1 − v^{H_{n}}, ψ_{0}(u, v) = 1.

Each [u^{p}]ψ_{n}(u, v)/\binom{n}{p} is a probability generating function, namely the coefficient of v^{k} in it is the probability that the smallest subtree of a random binary search tree of size n containing the root and a random sample of p nodes has total weight k. The factor 1 + u reflects the fact that the root can be in the sample or not, and the extra terms correspond to the case of p = 0; in this case the total weight must be 0.

If we denote

σ_{n}(u) = \frac{∂}{∂v} ψ_{n}(u, 1),

then

σ_{n}(u) = H_{n}(1 + u)^{n} + \frac{2(1 + u)}{n} ∑_{j=0}^{n−1} σ_{j}(u)σ_{n−1−j}(u).

This recursion can again be translated into a differential equation, viz.

\frac{∂}{∂z} G(z, u) = (1 + u)S(z(1 + u)) − S(z) + \frac{2(1 + u)}{1 − z(1 + u)}G(z, u), G(0, u) = 0,

again with S(z) = \frac{1}{(1−z)^{2}} log \frac{1}{1−z} + \frac{1}{(1−z)^{2}} . The solution is

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

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

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

It is again a routine task to read off the coefficients, and we get for p ≥ 1

[u^{p}]σ_{n}(u) = p\binom{n + 1}{p}[(H_{n+1} − H_{p})^{2} − (H_{n+1}^{(2)} − H_{p}^{(2)})]

+ (p − 1)\binom{n + 1}{p − 1}[(H_{n+1} − H_{p−1})^{2} − (H_{n+1}^{(2)} − H_{p−1}^{(2)})]

+ 2(p − 1)\binom{n + 2}{p}[H_{n+2} − H_{p}] + 4\binom{n + 1}{p}[H_{n+1} − H_{p}]\binom{n}{p}H_{n} − 2\binom{n}{p − 1}n.

In order to get the desired averages, one must divide that by \binom{n}{p}, which yields after simplifications

\frac{[u^{p}]σ_{n}(u)}{\binom{n}{p}} = X_{n,p} = \frac{p(n + 1)^{2}}{(n + 2 − p)(n + 1 − p)}((H_{n} − H_{p})^{2} − H_{n}^{(2)} + H_{p}^{(2)})

+ \frac{(1 + 2p)n^{2} + (1 + 8p)n + p(7 − p)}{(n + 2 − p)(n + 1 − p)}H_{n}

− \frac{2(n + 1)((p + 1)n + 2p + 1)}{(n + 2 − p)(n + 1 − p)}H_{p} − \frac{2p(n^{2} − pn − 2)}{(n + 2 − p)(n + 1 − p)}.

For fixed p (close to the Quickselect instance), this is roughly p log^{2} n; for p ∼ n (close to the Quicksort instance), this is roughly 2n, and for p ∼ ρn, with 0 < ρ < 1 it is asymptotic to (\frac{ρ}{(1−ρ)^{2}} log^{2} ρ − \frac{2ρ}{(1−ρ)^{2}} log ρ − \frac{2ρ}{1−ρ})n. The limit of this for ρ → 1 is 2n, which matches the intuition.

It is interesting to note the special instance p = 1:

\frac{n + 1}{n}(H_{n}^{2} − H_{n}^{(2)}) + \frac{n + 4}{n}H_{n} − 4.

Note that this is the same result as we obtained earlier for

\frac{1}{n} ∑_{j=1}^{n} a_{n,j},

as it should. The other interesting special case is p = n:

2n − H_{n}.

This is also clear, since there is no random sample involved, and only the average total weight of a random binary search tree has been computed.

References

[1] J. Fill. On the distribution of binary search trees under the random permutation model. Random Structures and Algorithms, 8:1–25, 1996.

[2] P. Grabner and H. Prodinger. Sorting algorithms for broadcast communications: Mathematical analysis. Theoretical Computer Science, to appear, 2000.

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

[4] P. Kirschenhofer and H. Prodinger. Comparisons in Hoare’s Find algorithm. Combinatorics, Probability, and Computing, 7:111–120, 1998.

[5] D. E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms. Addison-Wesley, 1968. Third edition, 1997.

[6] J. Lent and H. M. Mahmoud. Average–case analysis of multiple quickselect: An algorithm for finding order statistics. Statistics and Probability Letters, 28:299–310, 1996.

[7] A. Panholzer and H. Prodinger. A generating functions approach for the analysis of grand averages for multiple quickselect. Random Structures and Algorithms, 1999.

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

[9] R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley, 1996.

†Institut für Algebra und Computermathematik, Technische Universität Wien, Wiedner Hauptstraße 8–10, A- 1040 Wien, Austria.

  E-mail address: Alois.Panholzer@tuwien.ac.at

‡The John Knopfmacher Centre for Applicable Analysis and Number Theory, Mathematics Department, University of the Witwatersrand, P.O. Wits, 2050 Johannesburg, South Africa.

  E-mail address: helmut@gauss.cam.wits.ac.za
  WWW-address: http://www.wits.ac.za/helmut/index.htm