A GENERATING FUNCTIONS APPROACH FOR THE ANALYSIS OF GRAND AVERAGES FOR MULTIPLE QUICKSELECT

ALOIS PANHOLZER AND HELMUT PRODINGER

Abstract. Hoare’s Find algorithm can be used to select p specified order statistics j_{1}, …, j_{p} from a file of n elements simultaneously. Averaging over all \binom{n}{p} subsets of \{1, …, n\} defines the grand averages of the number of passes and comparisons. We use a generating functions approach to compute averages and variances of these parameters.

Additionally we sketch analogous developments for the instance of median-of-three partition and binary (Catalan) trees.

1. Introduction

Hoare’s Find algorithm (“Quickselect”) [2] uses the idea of Quicksort [3, 7] in order to select the jth element of a file of n elements. In each partitioning step, a certain element will be brought into its correct position k. In the process, elements are moved—those brought to the left of it are smaller, and those brought to the right are larger. If k = j, the element is found; if k < j, one has to continue on the right side, searching for the (j − k)th element; if k > j, one has to continue on the left side, still searching for the jth element.

Two parameters are of interest: the (average) number of passes (recursive calls) P [n; j] and the (average) number of comparisons C[n; j]. In Knuth’s book [7] we already find the values

P [n; j] = H_{j} + H_{n+1−j} − 1

and

C[n; j] = 2(n + 3 + (n + 1)H_{n} − (j + 2)H_{j} − (n + 3 − j)H_{n+1−j})

where H_{n} = 1 + \frac{1}{2} + ⋯ + \frac{1}{n} denotes the nth harmonic number; compare also [6] and [10].

Hoare’s idea can be extended as follows: Assume that we simultaneously search for the p elements with ranks j_{1}, j_{2}, …, j_{p} where 1 ≤ j_{1} < j_{2} < ⋯ < j_{p} ≤ n is a fixed set of p values. Then, according into which interval of the values j_{1}, …, j_{p} the pivot element falls, we may have found one of the elements and/or have to continue on both sides, but with smaller sets. The idea is quite simple; a nice description of the algorithm can be found in [8].

In [13], explicit formulæ for both the average number of passes P [n; j_{1}, …, j_{p}] and the average number of comparisons, C[n; j_{1}, …, j_{p}] were given. As a corollary, the grand averages,

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

and

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

were also computed (compare also [8]). However, the approach used in this previous paper was a mixture of guessing and proofs by induction.

In the present paper, we use a generating functions approach to attack the analysis of the grand averages directly. This enables us to compute the respective variances, something that was out of reach with the old method.

In both instances (passes resp. comparisons) we will use a trivariate generating function Φ(z, u, v) where the coefficient of [z^{n}/n!u^{p}v^{m}] is the number of permutations of {1, 2, …, n} and the subsets of p elements of {1, 2, …, n} such that the parameter of interest has value m.

Date: July 27, 1997.

Then, for fixed n and p with 0 ≤ p ≤ n,

\frac{[z^{n}u^{p}]Φ(z, u, v)}{\binom{n}{p}}

is the probability generating function of interest. Apart from the normalization factor \binom{n}{p}, the functions

M_{1}(z, u) = \frac{∂}{∂v} Φ(z, u, v)|_{v=1}

and

M_{2}(z, u) = \frac{∂^{2}}{∂v^{2}} Φ(z, u, v)|_{v=1}

are the generating functions of the expectations and the second factorial moments. To be more precise, the expectation E_{n,p} and the variance V_{n,p} are given by

\begin{aligned}E_{n,p} & = \frac{[z^{n}u^{p}]M_{1}(z, u)}{\binom{n}{p}} , \\ V_{n,p} & = \frac{[z^{n}u^{p}]M_{2}(z, u)}{\binom{n}{p}} + E_{n,p} − (E_{n,p})^{2} . \end{aligned}  (1)

(Since we decided not to overload the notation by an additional superscript [P] (for passes) and [C] (for comparisons), we have chosen the neutral E_{n,p} which means P_{n,p} or C_{n,p}, dependening on the section.)

For the following it is more suggestive to think about the binary search tree that is naturally associated to a permutation via the Quicksort procedure; the pivot element corresponds to the root, and the left (right) subfile corresponds to the left (right) subtree.

The last sections sketch analogous computations for median-of-three quickselect (see e.g. [4]); for the sake of shortness we confine ourselves to the instance of the expectations, since they are already quite complex. However, in principle, the variances could be obtained explicitly.

For reasons of comparisons we included also a section about binary (Catalan) trees. Things are a bit easier, since instead of differential equations we have to deal with algebraic equations. Again, we only give the expectations.

We also want to draw the reader’s attention to the papers [10] and [11] which attack quickselect resp. multiple quickselect with probabilistic tools. The main achievements in these papers are the establishing of the limiting distributions. However, we choose the present approach (suggested to us by Philippe Flajolet) since we find it more promising in order to get explicit results.

2. Average number of passes

Let ϕ_{p}(z, v) be the following generating function: The coefficient of z^{n}/n!v^{k} is the sum over all trees of size n and all labellings of exactly p nodes, such that the smallest subtree containing the root and these p nodes (which corresponds to the number of passes!) is k. Then we have the recurrence

ϕ′_{p}(z, v) = v ∑_{i=0}^{p} ϕ_{i}(z, v)ϕ_{p−i}(z, v) + v ∑_{i=0}^{p−1} ϕ_{i}(z, v)ϕ_{p−1−i}(z, v)  (2)

for p ≥ 1 and ϕ_{0}(z) = \frac{1}{1−z}. (The first sum refers to a nonlabelled, and the second sum to labelled root.)

Typically in such analyses, a first derivative appears because of the (uniform) splitting probability \frac{1}{n} (every element can be the root, with equal probability); the multiplication of the recursion then introduces a factor n on the left hand side, which means (in terms of generating functions) a derivative. This is quite classical (see for instance [7]) and we confine ourselves with this brief statement.

Observe that

\frac{1}{\binom{n}{p}}[z^{n}]ϕ_{p}(z, v)

are the probability generating functions of interest.

Then the trivariate generating function from the introduction is given by

Φ(z, u, v) = ∑_{p≥0} ϕ_{p}(z, v)u^{p} .

We get, by summing up the recursion (2),

Φ′(z, u, v) = v(1 + u)Φ^{2}(z, u, v) + \frac{1 − v}{(1 − z)^{2}}  (3)

with Φ(0, u, v) = 1.

Maple is capable to solve this differential equation: Lemma 1.

Φ(z, u, v) = \frac{Ω + 1 − 2v + (1 − z)^{Ω}(Ω − 1 + 2v)}{(Ω + 1 − 2v(1 + u) + (1 − z)^{Ω}(Ω − 1 + 2v(1 + u)))(1 − z)}  (4)

with

Ω = \sqrt{1 − 4v(1 + u)(1 − v)} .

Consequently we get

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

We have

[z^{n}] (\frac{1 + 2u}{1 − z(1 + u)} − \frac{2u}{(1 − z(1 + u))^{2}} − \frac{1}{1 − z} ) = (1 + 2u)(1 + u)^{n} − 2(n + 1)u(1 + u)^{n} − 1 .

Let us assume that p ≥ 1. Reading off the coefficient of u^{p} in the last formula, we obtain

\binom{n}{p} − 2n\binom{n}{p − 1} .

Now we turn to the logarithmic term. The factor of log \frac{1}{1−z} is

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

and the coefficient of u^{p} therein is

\frac{2pz^{p−1}}{(1 − z)^{p+1}} + \frac{2(p − 1)z^{p−2}}{(1 − z)^{p}} .

We observe the general formula (see e.g [1])

[z^{n}]\frac{1}{(1 − z)^{m+1}} log \frac{1}{1 − z} = \binom{n + m}{n} (H_{n+m} − H_{m})  (6)

and find so, searching for the coefficient of z^{n},

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

We collect both contributions, divide by \binom{n}{p} and get Theorem 2. For p ≥ 1 the average number E_{n,p} of passes to search for p random elements is given by

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

For p ≥ 0 we have E_{n,0} = 0.

This result appeared already in [13].

It is interesting to state the special cases p = 1 (Hoare’s Find algorithm or Quickselect) and p = n (Quicksort) explicitly.

4 A. PANHOLZER AND H. PRODINGER

Corollary 3.

E_{n,1} = 2 (1 + \frac{1}{n}) H_{n} − 3 ,
E_{n,n} = n .

By standard methods we obtain also the following asymptotic equivalents. Corollary 4.

E_{n,p} = 2p log n + 2γp − 2p − 2pH_{p} + 1 + O (\frac{log n}{n}) for p fixed ,
E_{n,p} = n − \frac{1}{3}l + O (\frac{log n}{n}) for l = n − p fixed ,
E_{n,p} = −\frac{2ρ(1 − ρ + log ρ)}{(1 − ρ)^{2}}n + \frac{ρ(4ρ log ρ + 2 log ρ − ρ^{2} − 4ρ + 5)}{(1 − ρ)^{3}} + O (\frac{log n}{n})
for p = ρn and 0 < ρ < 1.

(8)

3. Variance of the number of passes

From the function Φ(z, u, v) we find

\begin{aligned}M_{2}(z, u) = & − 2\frac{1 + 4u + 2u^{2}}{1 − z(1 + u)} − 2\frac{u(−3 + 2u)}{(1 − z(1 + u))^{2}} + 8\frac{u^{2}}{(1 − z(1 + u))^{3}} + 2\frac{1 + u}{1 − z} \\ & − (\frac{16u^{2}(1 + u)}{(1 − z(1 + u))^{3}} + \frac{4u(1 − u)(1 + u)}{(1 − z(1 + u))^{2}}) log \frac{1}{1 − z} \\ & + (\frac{8u^{2}(1 + u)^{2}}{(1 − z(1 + u))^{3}} + \frac{4u(1 + u)^{2}}{(1 − z(1 + u))^{2}} ) log^{2} \frac{1}{1 − z} . \end{aligned}  (9)

Now we assume that p ≥ 2 and read off the coefficient of z^{n}u^{p} in the non–logarithmic term, and divide by \binom{n}{p}, which gives

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

Furthermore, we consider the term with log \frac{1}{1−z}. The coefficient of u^{p} in the factor of log \frac{1}{1−z} is

−8p(p − 1)\frac{z^{p−2}}{(1 − z)^{p+1}} − 8(p − 1)(p − 2)\frac{z^{p−3}}{(1 − z)^{p}} − 4p\frac{z^{p−1}}{(1 − z)^{p+1}} + 4(p − 2)\frac{z^{p−3}}{(1 − z)^{p−1}} .

We are searching for the coefficient of z^{n} in this times log \frac{1}{1−z}, use the general formula (6) and obtain

\frac{−4p(n + 1)^{2}((2p − 1)n + 2p)(H_{n+1} − H_{p}) − 16(p − 1)^{2}n^{2} − 4(8p^{2} − 17p + 10)n − 4(4p^{2} − 9p + 6)}{(n + 3 − p)(n + 2 − p)(n + 1 − p)} .

For the term with the square of log \frac{1}{1−z} we get in a similar fashion

\frac{X}{(n + 4 − p)(n + 3 − p)(n + 2 − p)(n + 1 − p)}

with

X = 4p(n + 2)(n + 1)^{2}(pn + p + 2)(H_{n+1}^{2} − H_{n+1}^{(2)} + H_{p}^{2} + H_{p}^{(2)})
− 8(n + 1)^{2}H_{n+1}(n^{2}p^{2}H_{p} + n(p(3p + 2)H_{p} − (3p − 2)(p − 1)) + 2p(p + 2)H_{p} − 5p^{2} + 8p − 4)
− 8(n + 1)^{2}H_{p}((3p − 2)(p − 1)n + 5p^{2} − 8p + 4)
+ 8(n + 1)(p − 2)(n(3p − 4) + 4p − 7) .

For that we have used the general formula

[z^{n}]\frac{1}{(1 − z)^{m+1}} log^{2} \frac{1}{1 − z} = \binom{n + m}{m} ((H_{n+m} − H_{m})^{2} − (H_{n+m}^{(2)} − H_{m}^{(2)})) .  (10)

Dividing this by \binom{n}{p} leads to the following theorem; for p = 1 a similar but simpler computation, based on the formula

[u]M_{2}(z, u) = \frac{4z}{(1 − z)^{2}} − \frac{4}{(1 − z)^{2}} log \frac{1}{1 − z} + \frac{4}{(1 − z)^{2}} log^{2} \frac{1}{1 − z}

was used. Theorem 5. The variance of the number of passes when searching for a random set of p ≥ 2 elements with Hoare’s Find algorithm is given by

\begin{aligned}V_{n,p} & = −\frac{4p(n + 1)^{2}Ψ_{1}}{(n + 4 − p)(n + 3 − p)(n + 2 − p)^{2}(n + 1 − p)^{2}} (H_{n+1} − H_{p})^{2} \\ & + \frac{2(n + 1)^{2}Ψ_{2}}{(n + 4 − p)(n + 3 − p)(n + 2 − p)^{2}(n + 1 − p)}(H_{n+1} − H_{p}) \\ & − \frac{4p(n + 2)(n + 1)^{2}(pn + p + 2)}{(n + 4 − p)(n + 3 − p)(n + 2 − p)(n + 1 − p)}(H_{n+1}^{(2)} − H_{p}^{(2)}) \\ & + \frac{2(n + 1)^{2}Ψ_{3}}{(n + 4 − p)(n + 3 − p)(n + 2 − p)^{2}} \end{aligned}  (11)

with

\begin{aligned}Ψ_{1} & = (3p − 2)n^{3} − 2(p^{2} − 9p + 5)n^{2} − (p^{3} + 5p^{2} − 33p + 16)n − p^{3} − 5p^{2} + 20p − 8 , \\ Ψ_{2} & = pn^{3} + (11p^{2} − 13p + 8)n^{2} − (9p^{3} − 54p^{2} + 62p − 32)n − 3p^{4} − p^{3} + 38p^{2} − 56p + 32 , \\ Ψ_{3} & = (2p − 1)n^{2} − 2(5p^{2} − 15p + 8)n + 8p^{3} − 45p^{2} + 72p − 32 . \end{aligned}  (12)

For p = 1, the formula reads

V_{n,1} = −4\frac{n + 1}{n^{2}}H_{n+1}^{2} + \frac{2(n + 4)(n + 1)}{n^{2}}H_{n+1} − 4\frac{n + 1}{n}H_{n+1}^{(2)} + \frac{2(2n^{2} − n − 2)}{n^{2}} ;  (13)

for p = 0 we have V_{n,0} = 0.

Observe that for p = n (Quicksort) this formula simplifies to V_{n,n} = 0, as it should. Corollary 6.

V_{n,p} = 2p log n + 4p^{2}H_{p}^{(2)} − 2pH_{p} + 2pγ − \frac{2}{3}p^{2}π^{2} + O (\frac{log n}{n}) for p fixed ,
V_{n,p} = \frac{2}{9}l + O (\frac{1}{n}) for l = n − p fixed ,
V_{n,p} = (−\frac{4ρ^{2}(ρ + 3) log^{2} ρ}{(1 − ρ)^{5}} − \frac{2ρ(3ρ^{2} + 12ρ + 1) log ρ}{(1 − ρ)^{4}} − \frac{16ρ^{2}}{(1 − ρ)^{3}} ) n + O (1)
for p = ρn and 0 < ρ < 1.

(14)

4. Comparisons

If we have a tree with n nodes, there are costs of n − 1 comparisons, and then the additional costs, resulting from the subtrees. Typically, this leads, apart from other things, to a substitution z ↦ zv. Otherwise, we distinguish again whether or not the root is one of elements being sought.

The fundamental differential equation is thus

Φ′(z, u, v) = (1 + u)Φ^{2}(zv, u, v) + \frac{1}{(1 − z)^{2}} − \frac{1}{(1 − zv)^{2}} ,

with Φ(0, u, v) = 1. Now, we cannot solve that, but we can differentiate it with respect to v (followed by v := 1) and solve the resulting differential equation for M_{1}(z, u). (In the next section we will differentiate it twice, plug in the already known M_{1}(z, u) and solve the equation for M_{2}(z, u).)

\begin{aligned}M_{1}(z, u) & = −\frac{2(1 + u)(1 + 3u)}{(1 − z(1 + u))^{2}} log \frac{1}{1 − z} + \frac{2}{(1 − z(1 + u))^{2}} log \frac{1}{1 − z(1 + u)} \\ & + \frac{2(1 + 2u)}{u(1 − z)} − \frac{1}{(1 − z)^{2}} − \frac{2(1 + 3u + 3u^{2})}{u(1 − z(1 + u))} + \frac{3(1 + 2u)}{(1 − z(1 + u))^{2}} . \end{aligned}  (15)

From this, we read off the coefficients much in the same style as before, divide by \binom{n}{p} and obtain the expectations (known already from [13]). Theorem 7. For p ≥ 1 the average number E_{n,p} of comparisons to search for p random elements is given by

E_{n,p} = −\frac{2p(n + 1)(4n − p + 5)}{(n + 2 − p)(n + 1 − p)}H_{n+1} + \frac{2(n + 1)^{2}(n + 2p + 2)}{(n + 2 − p)(n + 1 − p)}H_{p} + \frac{n^{2} + (5p − 1)n + 3p}{n + 2 − p} .  (16)

For p = 0, we have E_{n,0} = 0.

Again, we note the special cases p = 1 and p = n. Corollary 8.

\begin{aligned}E_{n,1} & = 3n − 8 (1 + \frac{1}{n}) H_{n} + 13 , \\ E_{n,n} & = 2(n + 1)H_{n} − 4n . \end{aligned}  (17)

Corollary 9.

E_{n,p} = (2H_{p} + 1)n − 8p log n + 2(4p + 1)H_{p} + 3(2p − 1) − 8pγ + O (\frac{log n}{n}) for p fixed ,
E_{n,p} = 2n log n + 2(γ + 2)n + 2 log n + 1 + 2γ + O (\frac{log n}{n}) for l = n − p fixed ,
E_{n,p} = 2n log n + \frac{(4ρ + 2) log ρ + (2ρ^{2} − 4ρ + 2)γ − 5ρ^{2} + 4ρ + 1}{(1 − ρ)^{2}}n + 2 log n + O(1)
for p = ρn and 0 < ρ < 1.

(18)

5. Variance of the number of comparisons

As indicated in the last section, we can set up a differential equation for M_{2}(z, u), viz.

M′_{2}(z, u) = 2\frac{(1 + u)}{1 − z(1 + u)}M_{2}(z, u) + 8\frac{(3u + 1)^{2}(1 + u)^{3}}{(1 − z(1 + u))^{4}} log^{2} \frac{1}{1 − z}

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

− 8\frac{(3u + 1)(1 + u)^{2}(2z^{2}u^{2} − 9zu^{2} + 6u^{2} + 5z^{2}u + 9u − 14zu + 3 − 6z + 3z^{2})z}{(1 − z(1 + u))^{4}(1 − z)^{2}} log \frac{1}{1 − z}

+ 8\frac{(1 + u)(2z^{2}u^{2} − 9zu^{2} + 6u^{2} + 5z^{2}u + 9u − 14zu + 3 − 6z + 3z^{2})z}{(1 − z(1 + u))^{4}(1 − z)^{2}} log \frac{1}{1 − z(1 + u)}

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

(19)

with and M_{2}(0, u) = 0.

Now this time Maple does not do it automatically, since it cannot handle

∫_{0}^{z} \frac{log^{2}(1 − t)}{(1 − t(1 + u))^{2}} dt .

Ψ = 53 − 164z + 165u − 316z^{3}u^{2} − 242z^{3}u + 223u^{2} + 144u^{3} − 68z^{3} + 5z^{4} − 438zu^{3} + 174z^{2} + 592z^{2}u + 766z^{2}u^{2} − 700zu^{2} + 19z^{4}u + 27z^{4}u^{2} + 17z^{4}u^{3} − 534zu + 105u^{4}z^{2} + 36u^{4} + 4z^{4}u^{4} − 36z^{3}u^{4} + 453z^{2}u^{3} − 178z^{3}u^{3} − 108u^{4}z

However, by integration by parts this integral can be evaluated, and consequently we get the following solution. Lemma 10.

M_{2}(z, u) = 24\frac{(1 + u)^{3}}{(1 − z(1 + u))^{2}} ∫_{0}^{z} \frac{1}{1 − t(1 + u)} log \frac{1}{1 − t} dt

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

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

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

+ 4\frac{(1 + u) Ψ_{1}}{u(1 − z)(1 − z(1 + u))^{3}} log \frac{1}{1 − z}

− 8\frac{8z^{2}u^{3} + 9z^{2}u + z^{2} + 16z^{2}u^{2} − 20u^{2}z − 9u^{3}z − 2z − 14zu + 5u + 3u^{2} + 1}{u(1 − z)(1 − z(1 + u))^{3}} log \frac{1}{1 − z(1 + u)}

+ \frac{2}{3} \frac{z Ψ_{2}}{(1 − z)^{3}(1 − z(1 + u))^{3}}

(20)

with

Ψ_{1} = 10u^{4}z^{2} − 16u^{4}z + 31z^{2}u^{3} − 19u^{3}z − 20u^{3} − 7u^{2} + 35z^{2}u^{2} − 30u^{2}z + 8u − 24zu + 16z^{2}u + 2z^{2} − 4z + 2

and

Ψ_{2} = 12 − 330u^{3}z + 39z^{4}u^{3} − 12u^{4}z + 346z^{2}u^{3} − 173u^{3}z^{3} + 42z^{4}u^{2} + 15z^{4}u − 519u^{2}z + 478z^{2}u^{2} − 199u^{2}z^{3} − 36z − 237zu + 36z^{2} + 90u + 219z^{2}u − 87uz^{3} − 12z^{3} + 12z^{4}u^{4} − 49u^{4}z^{3} + 48u^{4}z^{2} + 198u^{2} + 120u^{3}.

We observe that

(1 + u) ∫_{0}^{z} \frac{1}{1 − t(1 + u)} log \frac{1}{1 − t} dt =

= log(1 − z(1 + u)) log(u) + dilog(\frac{1 + u}{u}) − dilog(\frac{1 − z + u − zu}{u}) − log(1 + u) log(1 − z(1 + u)) ,

which is more “closed form” but less useful, since for the coefficients the integrand is as good as the integral itself, since we can simply look for 1/n times the coefficient of z^{n−1}u^{p}.

We remark that Maple’s dilog function is related to the more common polylog function

L_{2}(z) = ∑_{n≥1} \frac{z^{n}}{n^{2}}

via dilog(1 − z) = L_{2}(z) (compare [9]).

The relevant formula for p ≥ 1 is this

\frac{1}{n}[z^{n−1}u^{p}]\frac{1}{1 − z(1 + u)} log \frac{1}{1 − z} = \frac{1}{n}\binom{n − 1}{p − 1}(H_{n−1} − H_{p−1}) .

For p = 0 it is slightly different;

\frac{1}{n}[z^{n−1}u^{0}]\frac{1}{1 − z(1 + u)} log \frac{1}{1 − z} = \frac{H_{n−1}}{n} .

On the other hand,

[z^{n}u^{p}]\frac{(1 + u)^{3}}{(1 − z(1 + u))^{2}} = (n + 1)\binom{n + 3}{p} .

The convolution of these two quantities can be performed by (the by now) standard tools.

There is only one sum,

λ_{n,p} = \frac{1}{\binom{n}{p}} ∑_{k=1}^{n} \frac{1}{k^{2}} \binom{n − k}{p} = \frac{1}{\binom{n}{p}}[z^{n}]\frac{z^{p}}{(1 − z)^{p+1}} L_{2}(z) ,  (21)

that has a “new” shape; we will relate it to more common quantities a bit later.

Observe that an analogous quantity has a well known evaluation:

\frac{1}{\binom{n}{p}} ∑_{k=1}^{n} \frac{1}{k} \binom{n − k}{p} = \frac{1}{\binom{n}{p}}[z^{n}]\frac{z^{p}}{(1 − z)^{p+1}} log \frac{1}{1 − z} = H_{n} − H_{p} .  (22)

After a lengthy routine calculation we arrive at the following theorem. Theorem 11. For p ≥ 2 the variance V_{n,p} of the number of comparisons to search for p random elements is given by

\begin{aligned}V_{n,p} & = −\frac{24(n + 1)^{2}(n + 2)}{(n + 1 − p)(n + 2 − p)}λ_{n+2,p} + \frac{4(n + 1)^{2}p Ψ_{1}}{(n + 2 − p)\underline{2} (n + 4 − p)\underline{4}} (H_{n+1} − H_{p})^{2} \\ & + \frac{2(n + 1)Ψ_{2}}{(n + 4 − p)\underline{4} (n + 2 − p)}(H_{n+1} − H_{p}) + \frac{4(n + 1)^{2}Ψ_{3}}{(n + 4 − p)\underline{4}} (H_{n+1}^{(2)} − H_{p}^{(2)}) \\ & − 2(n + 1)H_{p} − 4(n + 1)^{2}H_{p}^{(2)} + \frac{(n + 1)Ψ_{4}}{3(p + 1)^{2}(p + 2)(n + 2 − p) (n + 4 − p)\underline{4}} \end{aligned}  (23)

with

\begin{matrix}Ψ_{1} = & − 4n^{4} + (−27p − 13)n^{3} + (30p^{2} − 183p + 13)n^{2} \\ + (p^{3} + 108p^{2} − 379p + 70)n − 2p^{3} + 108p^{2} − 250p + 48 , \\ Ψ_{2} = & (54p − 28)n^{4} + (25p^{2} + 317p − 172)n^{3} + (−67p^{3} + 198p^{2} + 655p − 368)n^{2} \\ + (−13p^{4} − 107p^{3} + 252p^{2} + 618p − 320)n + p^{5} − 20p^{4} − 23p^{3} + 62p^{2} + 232p − 96 , \\ Ψ_{3} = & 6n^{3} + (−16p^{2} − 8p + 54)n^{2} \\ + (8p^{3} − 63p^{2} − 65p + 156)n − (p − 1)(p^{3} − 13p^{2} + 36p + 144) , \\ Ψ_{4} = & (21p^{3} + 80p^{2} + 81p − 2)n^{6} + (−105p^{4} − 76p^{3} + 815p^{2} + 1258p + 40)n^{5} \\ + (210p^{5} − 562p^{4} − 2173p^{3} + 2718p^{2} + 8125p + 886)n^{4} \\ + (−210p^{6} + 1036p^{5} − 223p^{4} − 9232p^{3} + 2283p^{2} + 25662p + 4096)n^{3} \\ + (105p^{7} − 500p^{6} + 2062p^{5} + 1352p^{4} − 18253p^{3} − 4600p^{2} + 43086p + 7972)n^{2} \\ + (−21p^{8} + 40p^{7} − 512p^{6} + 3390p^{5} + 3029p^{4} − 19638p^{3} − 11176p^{2} + 37736p + 7600)n \\ − 18p^{8} − 50p^{7} − 348p^{6} + 2232p^{5} + 2298p^{4} − 8886p^{3} − 6540p^{2} + 13616p + 2880 . \end{matrix}  (24)

For p = 1 we get

V_{n,1} = −\frac{16(n + 1)(n + 4)}{n^{2}}H_{n}^{2} + \frac{12(9n + 17)}{n}H_{n} − \frac{48(n + 1)}{n}H_{n}^{(2)} + n^{2} − 10n − 47 ;  (25)

and for p = 0 we have V_{n,0} = 0.

Observe that for p = n the formula simplifies to

V_{n,n} = −2(n + 1)H_{n} − 4(n + 1)^{2}H_{n}^{(2)} + (7n + 13)n .  (26)

We can rewrite the quantity λ_{n,p} as follows: Proposition 1.

λ_{n,p} = −\frac{1}{2}[H_{n}^{2} − H_{n}^{(2)} − H_{n−p}^{2} − H_{n−p}^{(2)}] + ∑_{j=1}^{p−1} \frac{H_{j}}{j + n + 1 − p} .  (27)

ANALYSIS OF GRAND AVERAGES FOR MULTIPLE QUICKSELECT 9

Proof. We write

\binom{n − k}{p} = \frac{n − k}{p} \binom{n − 1 − k}{p − 1}

and get consequently the recursion

λ_{n,p} = λ_{n−1,p−1} − \frac{1}{n}(H_{n−1} − H_{p−1}) .

Unwinding this we get

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

Since

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

the result readily follows.

In order to handle the sum ∑_{j=1}^{p−1} \frac{H_{j}}{n−p+1+j} asymptotically for either p or l = n − p fixed or for a fixed ratio ρ = \frac{p}{n} with 0 < ρ < 1 as n → ∞ we state a few relations that are easy to prove (but not so easy to find) by generating functions and/or can be found in [5]. Proposition 2.

∑_{j=1}^{p−1} \frac{H_{j}}{n − p + 1 + j} = H_{n}H_{p} − ∑_{j=1}^{p} \frac{H_{n−p+j}}{j} ,  (28a)
∑_{j=1}^{p−1} \frac{H_{j}}{n − p + 1 + j} = ∑_{j=1}^{p} \frac{H_{n−j}}{j} − \frac{1}{n + 1 − p}(H_{n} − H_{p} − H_{n+1−p}) − H_{p}H_{n+1−p} + H_{n}H_{n+1−p}
− \frac{1}{2}(H_{n}^{2} − H_{n}^{(2)}) − \frac{1}{2}(H_{n+1−p}^{2} + H_{n+1−p}^{(2)}) ,  (28b)

\begin{aligned}∑_{j=1}^{p−1} \frac{H_{j}}{n − p + 1 + j} & = − ∑_{j=p+1}^{n} \frac{H_{j−p}}{j} − \frac{1}{2}(H_{p−1}^{2} + H_{p−1}^{(2)}) + H_{n}H_{p−1} + \frac{H_{n−p}}{p} \\ & − \frac{1}{n + 1 − p}(H_{n} − H_{p} − H_{n+1−p}) − H_{p}H_{n+1−p} + H_{n}H_{n+1−p} \\ & − \frac{1}{2}(H_{n+1−p}^{2} + H_{n+1−p}^{(2)}) , \end{aligned}  (28c)

For fixed p we can use the definition and find

∑_{j=1}^{p−1} \frac{H_{j}}{n − p + 1 + j} = \frac{p(H_{p} − 1)}{n} + O (\frac{1}{n^{2}} ) for n → ∞ .  (29)

For fixed l = n − p we compute

∑_{j=p+1}^{n} \frac{H_{j−p}}{j} = ∑_{j=1}^{l} \frac{H_{j}}{n + j − l} = ∑_{j=1}^{l} \frac{H_{j}}{n} (1 + O(\frac{1}{n})) = \frac{(l + 1)H_{l} − l}{n} + O (\frac{1}{n^{2}} ) ,  (30)

and use (28c) to find

∑_{j=1}^{p−1} \frac{H_{j}}{n − p + 1 + j} = \frac{1}{2} log^{2} n + γ log n − \frac{π^{2}}{12} + \frac{H_{l+1}}{l + 1} − \frac{1}{2}H_{l+1}^{2} + \frac{γ^{2}}{2} − \frac{1}{2}H_{l+1}^{(2)} + \frac{log n}{2n} + \frac{γ}{2n}

− \frac{lH_{l}}{n} − \frac{l}{(l + 1)n} + \frac{1}{2n} + \frac{lH_{l+1}}{n} + \frac{l}{n} + O (\frac{log n}{n^{2}}) for n → ∞ .

(31)

For a fixed ratio ρ = \frac{p}{n} with 0 < ρ < n we use the expansion

∑_{j=1}^{p} \frac{H_{n−j}}{j} = log^{2} n + (2γ + log ρ) log n + γ^{2} + γ log ρ − L_{2}(ρ) + o(1)  (32)

from [5]. With this and equation (28b) we get

∑_{j=1}^{p−1} \frac{H_{j}}{n − p + 1 + j} = − log(1 − ρ) log n − \frac{1}{2} log^{2}(1 − ρ) − γ log(1 − ρ) − log ρ log(1 − ρ)
− L_{2}(ρ) + o(1) for n → ∞ .

(33)

Combining these formulæ with the standard expansions for harmonic numbers we get the following lemma. Lemma 12. The quantity λ_{n,p} has the following asymptotic equivalents:

λ_{n,p} = \frac{π^{2}}{6} + O (\frac{log n}{n}) for p fixed ,
λ_{n,p} = \frac{l}{n} + O (\frac{1}{n^{2}} ) for l = n − p fix ,
λ_{n,p} = L_{2}(1 − ρ) + o(1) for p = ρn and 0 < ρ < 1.

(34)

With this we get the following corollary. Corollary 13. The variance V_{n,p} of the number of comparisons is asymptotically given by

V_{n,p} = (\frac{21p^{3} + 80p^{2} + 81p − 2}{3(p + 1)^{2}(p + 2)} − 4H_{p}^{(2)}) n^{2} + O(n) for p fixed ,
V_{n,p} = (\frac{7l^{4} + 70l^{3} + 245l^{2} + 368l + 168}{(l + 4)\underline{4}} − \frac{2}{3}π^{2}) n^{2} + O(n log n) for l = n − p fixed ,
V_{n,p} = (7 − \frac{2}{3}π^{2}) n^{2} + O(n log n) for p = ρn and 0 < ρ < 1.

(35)

Remark. The instance ‘p fixed’ of the above corollary appears in [11].

6. Median of three partition – passes

As it says, one takes a random sample of 3 elements and uses the median as the pivot element. See [7, 1] for that in the context of Quicksort and [4, 12] in the context of Quickselect.

The only thing that changes are the splitting probabilities. Instead of \frac{1}{n} they are in this instance

\frac{(k − 1)(n − k)}{\binom{n}{3}} .

Now \binom{n}{3} moves as a factor to the left hand side and produces \frac{1}{6} times a third derivative. In this way we find the following differential equation of interest:

\begin{matrix}\frac{1}{6} \frac{∂^{3}}{∂z^{3}} Φ(z, u, v) = v(1 + u) (\frac{∂}{∂z} Φ(z, u, v))^{2} + \frac{1 − v}{(1 − z)^{4}} , \\ Φ(0, u, v) = 1 , \frac{∂}{∂z} Φ(z, u, v)|_{z=0} = 1 + uv , \frac{∂^{2}}{∂z^{2}} Φ(z, u, v)|_{z=0} = 2(1 + 2uv + u^{2}v) . \end{matrix}  (36)

It is natural to consider the function

Ψ(z, u, v) = \frac{∂}{∂z} Φ(z, u, v) .

For the evaluation of the expectated values we define

G(z, u) = \frac{∂}{∂v} Ψ(z, u, v)|_{v=1} ;

to get it, we have to solve the following differential equation

\begin{matrix}\frac{1}{6} \frac{∂^{2}}{∂z^{2}} G(z, u) = \frac{2(1 + u)^{2}}{(1 − z(1 + u))^{2}} G(z, u) + \frac{(1 + u)^{3}}{(1 − z(1 + u))^{4}} − \frac{1}{(1 − z)^{4}} , \\ G(0, u) = u , \frac{∂}{∂z} G(z, u)|_{z=0} = 4u + 2u^{2} . \end{matrix}  (37)

Therefore we obtain

\begin{aligned}G(z, u) & = \frac{12}{7} \frac{(u + 1)^{2} p_{1}(z, u)}{(1 − z(1 + u))^{3} u^{6}} log \frac{1}{1 − z} \\ & + \frac{60}{7} \frac{(u + 1)^{2} (1 − z(1 + u))^{4}}{u^{6}} log \frac{1}{1 − z(1 + u)} − \frac{1}{7} \frac{p_{2}(z, u)}{(1 − z(1 + u))^{3} (1 − z)^{2} u^{5}} , \end{aligned}  (38)

with

p_{1}(z, u) = 5z^{7}u^{7} + 35z^{7}u^{6} + 105z^{7}u^{5} + 175z^{7}u^{4} + 175z^{7}u^{3} + 105z^{7}u^{2} + 35z^{7}u + 5z^{7} − 35z^{6}u^{6} − 210z^{6}u^{5} − 525z^{6}u^{4} − 700z^{6}u^{3} − 525z^{6}u^{2} − 210z^{6}u − 35z^{6} + 105z^{5}u^{5} + 525z^{5}u^{4} + 1050z^{5}u^{3} + 1050z^{5}u^{2} + 525z^{5}u + 105z^{5} − 175z^{4}u^{4} − 700z^{4}u^{3} − 1050z^{4}u^{2} − 700z^{4}u − 175z^{4} + 175z^{3}u^{3} + 525z^{3}u^{2} + 525z^{3}u + 175z^{3} − 105z^{2}u^{2} − 210z^{2}u − 105z^{2} + 35zu + 35z + 2u^{7} − 5,

p_{2}(z, u) = 2z^{9}u^{13}+13z^{9}u^{12}+37z^{9}u^{11}+58z^{9}u^{10}+62z^{9}u^{9}+202z^{9}u^{8}+998z^{9}u^{7}+2872z^{9}u^{6}+5018z^{9}u^{5}+5637z^{9}u^{4}+4125z^{9}u^{3}+1910z^{9}u^{2}+ 510z^{9}u+60z^{9}−4z^{8}u^{13}−40z^{8}u^{12}−151z^{8}u^{11}−298z^{8}u^{10}−348z^{8}u^{9}−554z^{8}u^{8}−2720z^{8}u^{7}−9846z^{8}u^{6}−20998z^{8}u^{5}−27878z^{8}u^{4}−23545z^{8}u^{3}− 12360z^{8}u^{2} − 3690z^{8}u − 480z^{8} + 2z^{7}u^{13} + 41z^{7}u^{12} + 233z^{7}u^{11} + 611z^{7}u^{10} + 867z^{7}u^{9} + 847z^{7}u^{8} + 2611z^{7}u^{7} + 12483z^{7}u^{6} + 34481z^{7}u^{5} + 56212z^{7}u^{4} +56240z^{7}u^{3} +34110z^{7}u^{2} +11550z^{7}u+1680z^{7} −14z^{6}u^{12} −161z^{6}u^{11} −630z^{6}u^{10} −1183z^{6}u^{9} −1170z^{6}u^{8} −1259z^{6}u^{7} −6966z^{6}u^{6} − 27635z^{6}u^{5} −58808z^{6}u^{4} −72400z^{6}u^{3} −52060z^{6}u^{2} −20370z^{6}u−3360z^{6} +42z^{5}u^{11} +329z^{5}u^{10} +917z^{5}u^{9} +1195z^{5}u^{8} +745z^{5}u^{7} +1557z^{5}u^{6} + 10729z^{5}u^{5} + 33377z^{5}u^{4} + 53725z^{5}u^{3} + 47550z^{5}u^{2} + 22050z^{5}u + 4200z^{5} − 70z^{4}u^{10} − 385z^{4}u^{9} − 740z^{4}u^{8} − 605z^{4}u^{7} − 180z^{4}u^{6} − 1595z^{4}u^{5} − 9610z^{4}u^{4} − 22625z^{4}u^{3} − 26160z^{4}u^{2} − 14910z^{4}u − 3360z^{4} + 70z^{3}u^{9} + 267z^{3}u^{8} + 324z^{3}u^{7} + 127z^{3}u^{6} + 1070z^{3}u^{4} + 4870z^{3}u^{3} + 8210z^{3}u^{2} + 6090z^{3}u+1680z^{3}−78z^{2}u^{8}−149z^{2}u^{7}−71z^{2}u^{6}−390z^{2}u^{3}−1260z^{2}u^{2}−1350z^{2}u−480z^{2}+24zu^{8}+55zu^{7}+31zu^{6}+60zu^{2}+120zu+60z−7u^{6}.

Reading off the coefficients we find Theorem 14. The expected value E_{n,p} of the number of passes in Multiple Quickselect with medianof-three partition is given by

\begin{matrix}E_{n,p} = \frac{12}{7} \frac{(n + 1)^{2} p}{(n − p + 1) (n − p + 2)}(H_{n} − H_{p}) \\ − \frac{1}{7} \frac{r(n, p)}{n\underline{6} (p + 6)\underline{6} (n + 1 − p) (n + 2 − p)} , for n ≥ 6 and 1 ≤ p ≤ n , \end{matrix}  (39)

\begin{matrix}E_{1,1} = 1 , E_{2,1} = 1 , E_{2,2} = 1 , E_{3,1} = \frac{5}{3} , E_{3,2} = \frac{7}{3} , E_{3,3} = 3 , \\ E_{4,1} = \frac{7}{4} , E_{4,2} = \frac{7}{3} , E_{4,3} = \frac{11}{4} , E_{4,4} = 3 , \\ E_{5,1} = \frac{51}{25} , E_{5,2} = \frac{141}{50} , E_{5,3} = \frac{17}{5} , E_{5,4} = \frac{96}{25} , E_{5,5} = \frac{21}{5} , \end{matrix}  (40)

with

r(n, p) = 12n^{8}p^{7} + 247n^{8}p^{6} + 1995n^{8}p^{5} + 7945n^{8}p^{4} + 15813n^{8}p^{3} + 13048n^{8}p^{2} − 180n^{8}p − 5040n^{8} − 12n^{7}p^{8} − 422n^{7}p^{7} − 5598n^{7}p^{6} − 37058n^{7}p^{5}−131838n^{7}p^{4}−244328n^{7}p^{3}−191592n^{7}p^{2}+14688n^{7}p+60480n^{7}+175n^{6}p^{8}+4536n^{6}p^{7}+48328n^{6}p^{6}+271362n^{6}p^{5}+850885n^{6}p^{4}+ 1429134n^{6}p^{3} + 1000692n^{6}p^{2} − 97272n^{6}p − 272160n^{6} − 945n^{5}p^{8} − 21560n^{5}p^{7} − 200550n^{5}p^{6} − 977060n^{5}p^{5} − 2648205n^{5}p^{4} − 3784340n^{5}p^{3} − 2220540n^{5}p^{2} +236880n^{5}p+544320n^{5} +2275n^{4}p^{8} +48048n^{4}p^{7} +403333n^{4}p^{6} +1708875n^{4}p^{5} +3752980n^{4}p^{4} +3919377n^{4}p^{3} +1317372n^{4}p^{2} − 477540n^{4}p − 347760n^{4} − 2163n^{3}p^{8} − 42098n^{3}p^{7} − 309372n^{3}p^{6} − 991802n^{3}p^{5} − 1085637n^{3}p^{4} + 989548n^{3}p^{3} + 2813412n^{3}p^{2} + 1168272n^{3}p − 362880n^{3} + 70n^{2}p^{8} − 2196n^{2}p^{7} − 73908n^{2}p^{6} − 601272n^{2}p^{5} − 2321130n^{2}p^{4} − 4860324n^{2}p^{3} − 5002312n^{2}p^{2} − 1360368n^{2}p + 624960n^{2} + 600np^{8} + 15120np^{7} + 127440np^{6} + 574560np^{5} + 1625400np^{4} + 2756880np^{3} + 2229600np^{2} + 342720np − 241920n + 1440p^{7} + 10080p^{6} + 10080p^{5} − 50400p^{4} − 80640p^{3} + 40320p^{2} + 69120p.

Again we note the special cases. Corollary 15.

\begin{aligned}E_{n,1} & = \frac{12}{7} \frac{n + 1}{n}H_{n} − \frac{131n − 2}{49n} , \\ E_{n,n} & = \frac{6}{7}n − \frac{1}{7} . \end{aligned}  (41)

Related formulæ can be found in [1, 7, 4].

Corollary 16.

E_{n,p} = \frac{12}{7}p log n − \frac{12}{7}pH_{p} + \frac{12}{7}pγ − \frac{12p^{7} + 247p^{6} + 1995p^{5} + 7945p^{4} + 15813p^{3} + 13048p^{2} − 180p − 5040}{7 (p + 6)\underline{6}} (42)

+ O (\frac{log n}{n}) for p fixed ,

E_{n,p} = \frac{6}{7}n − \frac{2}{7}l − \frac{1}{7} + O (\frac{log n}{n}) for l = n − p fixed ,

E_{n,p} = \frac{12}{7} \frac{ρ(ρ − 1 − log ρ)}{(1 − ρ)^{2}}n + O(1) for fixed ρ = \frac{p}{n} with 0 < ρ < 1 .

(43)

7. Median of three – comparisons

In this instance the differential equation is

\begin{matrix}\frac{1}{6} \frac{∂^{3}}{∂z^{3}} Φ(z, u, v) = (1 + u) (\frac{∂}{∂z} Φ(zv, u, v))^{2} + \frac{1}{(1 − z)^{4}} − \frac{v^{2}}{(1 − zv)^{4}} , \\ Φ(0, u, v) = 1 , \frac{∂}{∂z} Φ(z, u, v)|_{z=0} = 1 + u , \frac{∂^{2}}{∂z^{2}} Φ(z, u, v)|_{z=0} = 2(1 + 2uv + u^{2}v) . \end{matrix}  (44)

With

Ψ(z, u, v) = \frac{∂}{∂z} Φ(z, u, v)

and

G(z, u) = \frac{∂}{∂v} Ψ(z, u, v)|_{v=1}

we get

\begin{matrix}\frac{1}{6} \frac{∂^{2}}{∂z^{2}} G(z, u) = \frac{2(1 + u)^{2}}{(1 − z(1 + u))^{2}} G(z, u) + \frac{2(1 + u)^{3}(1 + z(1 + u))}{(1 − z(1 + u))^{5}} − \frac{2(1 + z)}{(1 − z)^{5}} , \\ G(0, u) = 0 , \frac{∂}{∂z} G(z, u)|_{z=0} = 4u + 2u^{2} . \end{matrix}  (45)

and furthermore

\begin{aligned}G(z, u) & = \frac{24}{7} \frac{(1 + u)^{2} p_{1}(z, u)}{(1 − z(1 + u))^{3} u^{7}} log \frac{1}{1 − z} − \frac{24}{7} \frac{(1 + u) p_{2}(z, u)}{(1 − z(1 + u))^{3} u^{7}} log \frac{1}{1 − z(1 + u)} \\ & − \frac{2}{49} \frac{z g_{3}(z, u)}{(1 − z(1 + u))^{3} (1 − z)^{3} u^{6}} , \end{aligned}  (46)

with

p_{1}(z, u) = 10z^{7}u^{8} + 85z^{7}u^{7} + 315z^{7}u^{6} + 665z^{7}u^{5} + 875z^{7}u^{4} + 735z^{7}u^{3} + 385z^{7}u^{2} + 115z^{7}u + 15z^{7} − 70z^{6}u^{7} − 525z^{6}u^{6} − 1680z^{6}u^{5} − 2975z^{6}u^{4} −3150z^{6}u^{3} −1995z^{6}u^{2} −700z^{6}u−105z^{6} +210z^{5}u^{6} +1365z^{5}u^{5} +3675z^{5}u^{4} +5250z^{5}u^{3} +4200z^{5}u^{2} +1785z^{5}u+315z^{5} −350z^{4}u^{5} − 1925z^{4}u^{4} − 4200z^{4}u^{3} − 4550z^{4}u^{2} − 2450z^{4}u − 525z^{4} + 350z^{3}u^{4} + 1575z^{3}u^{3} + 2625z^{3}u^{2} + 1925z^{3}u + 525z^{3} − 210z^{2}u^{3} − 735z^{2}u^{2} − 840z^{2}u − 315z^{2} + 70zu^{2} + 175zu + 105z − 3u^{8} − u^{7} − 10u − 15,

p_{2}(z, u) = 10z^{7}u^{9} + 95z^{7}u^{8} + 400z^{7}u^{7} + 980z^{7}u^{6} + 1540z^{7}u^{5} + 1610z^{7}u^{4} + 1120z^{7}u^{3} + 500z^{7}u^{2} + 130z^{7}u + 15z^{7} − 70z^{6}u^{8} − 595z^{6}u^{7} − 2205z^{6}u^{6} − 4655z^{6}u^{5} − 6125z^{6}u^{4} − 5145z^{6}u^{3} − 2695z^{6}u^{2} − 805z^{6}u − 105z^{6} + 210z^{5}u^{7} + 1575z^{5}u^{6} + 5040z^{5}u^{5} + 8925z^{5}u^{4} + 9450z^{5}u^{3} + 5985z^{5}u^{2} +2100z^{5}u+315z^{5} −350z^{4}u^{6} −2275z^{4}u^{5} −6125z^{4}u^{4} −8750z^{4}u^{3} −7000z^{4}u^{2} −2975z^{4}u−525z^{4} +350z^{3}u^{5} +1925z^{3}u^{4} +4200z^{3}u^{3} + 4550z^{3}u^{2} + 2450z^{3}u + 525z^{3} − 210z^{2}u^{4} − 945z^{2}u^{3} − 1575z^{2}u^{2} − 1155z^{2}u − 315z^{2} + 70zu^{3} + 245zu^{2} + 280zu + 105z − u^{7} − 10u^{2} − 25u − 15,

p_{3}(z, u) = 2z^{9}u^{14} + 16z^{9}u^{13} + 49z^{9}u^{12} + 91z^{9}u^{11} + 14z^{9}u^{10} − 2450z^{9}u^{9} − 17374z^{9}u^{8} − 60926z^{9}u^{7} − 130534z^{9}u^{6} − 184296z^{9}u^{5} − 176127z^{9}u^{4} − 113365z^{9}u^{3} − 47250z^{9}u^{2} − 11550z^{9}u − 1260z^{9} − 6z^{8}u^{14} − 62z^{8}u^{13} − 245z^{8}u^{12} − 518z^{8}u^{11} − 434z^{8}u^{10} + 6804z^{8}u^{9} + 60998z^{8}u^{8} + 253940z^{8}u^{7} + 631002z^{8}u^{6} + 1015546z^{8}u^{5} + 1091195z^{8}u^{4} + 780850z^{8}u^{3} + 358470z^{8}u^{2} + 95760z^{8}u + 11340z^{8} + 6z^{7}u^{14} + 90z^{7}u^{13} + 483z^{7}u^{12} + 1260z^{7}u^{11} + 1701z^{7}u^{10} − 5439z^{7}u^{9} − 78855z^{7}u^{8} − 415647z^{7}u^{7} − 1244265z^{7}u^{6} − 2342319z^{7}u^{5} − 2882880z^{7}u^{4} − 2326065z^{7}u^{3} − 1189230z^{7}u^{2} − 350280z^{7}u − 45360z^{7} − 2z^{6}u^{14} − 58z^{6}u^{13} − 469z^{6}u^{12} − 1652z^{6}u^{11} − 2989z^{6}u^{10} − 742z^{6}u^{9} + 43617z^{6}u^{8} + 332316z^{6}u^{7} + 1274453z^{6}u^{6} + 2914716z^{6}u^{5} + 4216380z^{6}u^{4} + 3907820z^{6}u^{3} + 2256450z^{6}u^{2} + 740880z^{6}u + 105840z^{6} + 14z^{5}u^{13} + 224z^{5}u^{12} + 1211z^{5}u^{11} +2961z^{5}u^{10} +3640z^{5}u^{9} −7161z^{5}u^{8} −128646z^{5}u^{7} −709779z^{5}u^{6} −2096234z^{5}u^{5} −3701635z^{5}u^{4} −4043165z^{5}u^{3} −2685690z^{5}u^{2} − 996660z^{5}u−158760z^{5} −42z^{4}u^{12} −462z^{4}u^{11} −1743z^{4}u^{10} −2898z^{4}u^{9} −2205z^{4}u^{8} +18648z^{4}u^{7} +201453z^{4}u^{6} +860622z^{4}u^{5} +1971627z^{4}u^{4} + 2635290z^{4}u^{3} +2065350z^{4}u^{2} +882000z^{4}u+158760z^{4} +70z^{3}u^{11} +560z^{3}u^{10} +1484z^{3}u^{9} +1568z^{3}u^{8} +574z^{3}u^{7} −22330z^{3}u^{6} −183015z^{3}u^{5} − 609210z^{3}u^{4} −1058575z^{3}u^{3} −1015770z^{3}u^{2} −511560z^{3}u−105840z^{3} −70z^{2}u^{10} −868z^{2}u^{9} −1526z^{2}u^{8} −728z^{2}u^{7} +14980z^{2}u^{5} +96110z^{2}u^{4} + 243040z^{2}u^{3} + 303030z^{2}u^{2} + 186480z^{2}u + 45360z^{2} + 672zu^{9} + 1491zu^{8} + 819zu^{7} − 5460zu^{4} − 26670zu^{3} − 48300zu^{2} − 38430zu − 11340z − 252u^{9} − 553u^{8} − 350u^{7} + 840u^{3} + 2940u^{2} + 3360u + 1260.

Reading off the coefficients we get Theorem 17. The expected value E_{n,p} of the number of comparisons in Multiple Quickselect with median-of-three partition is given by

\begin{matrix}E_{n,p} = −\frac{12}{7} \frac{(n + 1) (4n − p + 5) p}{(n − p + 1) (n − p + 2)}H_{n} + \frac{12}{7} \frac{(n + 1)^{2} (n + 2p + 2)}{(n − p + 2) (n − p + 1)}H_{p} \\ + \frac{1}{49} \frac{r(n, p)}{n\underline{6} (p + 7)\underline{7} (n + 1 − p) (n + 2 − p)} , for n ≥ 6 and 1 ≤ p ≤ n , \end{matrix}  (47)

\begin{matrix}E_{1,1} = 0 , E_{2,1} = 1 , E_{2,2} = 1 , E_{3,1} = 2 , E_{3,2} = 2 , E_{3,3} = 2 , \\ E_{4,1} = \frac{7}{2} , E_{4,2} = \frac{23}{6} , E_{4,3} = 4 , E_{4,4} = 4 , \\ E_{5,1} = \frac{126}{25} , E_{5,2} = \frac{141}{25} , E_{5,3} = \frac{148}{25} , E_{5,4} = 6 , E_{5,5} = 6 . \end{matrix}  (48)

with

r(n, p) = 37n^{9}p^{7} + 1036n^{9}p^{6} + 11914n^{9}p^{5} + 72520n^{9}p^{4} + 250453n^{9}p^{3} + 485884n^{9}p^{2} + 483516n^{9}p + 246960n^{9} + 178n^{8}p^{8} + 4423n^{8}p^{7} + 41608n^{8}p^{6} + 168238n^{8}p^{5} + 105322n^{8}p^{4} − 1459913n^{8}p^{3} − 5040948n^{8}p^{2} − 6877548n^{8}p − 3210480n^{8} − 215n^{7}p^{9} − 8651n^{7}p^{8} − 139688n^{7}p^{7} − 1178702n^{7}p^{6} − 5578475n^{7}p^{5} − 14341019n^{7}p^{4} − 15631422n^{7}p^{3} + 8099412n^{7}p^{2} + 31066920n^{7}p + 16299360n^{7} + 3192n^{6}p^{9} + 103600n^{6}p^{8} + 1417654n^{6}p^{7}+10600072n^{6}p^{6}+46767364n^{6}p^{5}+121653280n^{6}p^{4}+168818566n^{6}p^{3}+84897288n^{6}p^{2}−38913336n^{6}p−40007520n^{6}−17780n^{5}p^{9}− 529760n^{5}p^{8} − 6609827n^{5}p^{7} − 44872436n^{5}p^{6} − 179988074n^{5}p^{5} − 428908760n^{5}p^{4} − 581222523n^{5}p^{3} − 387896964n^{5}p^{2} − 53621316n^{5}p + 43711920n^{5}+45570n^{4}p^{9}+1288672n^{4}p^{8}+15030547n^{4}p^{7}+93440452n^{4}p^{6}+331748032n^{4}p^{5}+679515928n^{4}p^{4}+772514743n^{4}p^{3}+431025588n^{4}p^{2}+ 83709108n^{4}p+740880n^{4} −51485n^{3}p^{9} −1380029n^{3}p^{8} −14864922n^{3}p^{7} −80529498n^{3}p^{6} −228035325n^{3}p^{5} −283648701n^{3}p^{4} +46816532n^{3}p^{3} + 407511188n^{3}p^{2} +191861280n^{3}p−48404160n^{3} +16758n^{2}p^{9} +376590n^{2}p^{8} +2608656n^{2}p^{7} +2675148n^{2}p^{6} −62468994n^{2}p^{5} −381548370n^{2}p^{4} − 945477876n^{2}p^{3} − 1039134408n^{2}p^{2} − 367655184n^{2}p + 42477120n^{2} + 3960np^{9} + 169560np^{8} + 2311200np^{7} + 18975600np^{6} + 99068760np^{5} + 310910040np^{4} + 552004560np^{3} + 497069280np^{2} + 161881920np − 11854080n + 20160p^{8} + 161280p^{7} + 282240p^{6} − 564480p^{5} − 1834560p^{4} − 564480p^{3} + 1532160p^{2} + 967680p.

Again, we list the two prominent special cases. Corollary 18.

\begin{aligned}E_{n,1} & = \frac{245n^{2} + 1111n − 2}{98n} − \frac{48}{7} \frac{n + 1}{n}H_{n} , \\ E_{n,n} & = \frac{12}{7}(n + 1)H_{n} − \frac{173}{49}n + \frac{9}{49} . \end{aligned}  (49)

And here are the asymptotics. Corollary 19.

E_{n,p} = (\frac{12}{7}H_{p} + \frac{37p^{7} + 1036p^{6} + 11914p^{5} + 72520p^{4} + 250453p^{3} + 485884p^{2} + 483516p + 246960}{49 (p + 7)\underline{7}}) n (50)

+ O (log n) for p fixed ,  (51)
E_{n,p} = \frac{12}{7}n log n + \frac{84γ − 173}{49}n + \frac{12}{7} log n + \frac{51}{49} + \frac{12}{7}γ + O (\frac{log n}{n}) for l = n − p fixed, ,

E_{n,p} = \frac{12}{7}n log n + \frac{168ρ log ρ + 84 log ρ + 84γρ^{2} − 168γρ + 84γ − 215ρ^{2} + 178ρ + 37}{49(1 − ρ)^{2}}n

+ O(log n) for fixed ρ = \frac{p}{n} with 0 < ρ < 1 .

(52)

8. Binary trees

In this section we briefly sketch – for the reason of comparison – the analogous questions for the instance of binary (Catalan) trees, enumerated by Catalan numbers

b_{n} = \frac{1}{n + 1}\binom{2n}{n};

note that

B(z) = ∑_{n≥0} b_{n}z^{n} = \frac{1 − \sqrt{1 − 4z}}{2z} .

Then the equation for the number of passes is

F (z, u, v) = zv(1 + u)F^{2}(z, u, v) + v + (1 − v)B(z) .  (53)

The normalization factor is this time \binom{n}{p}b_{n}. This quadratic equation is of course readily solved; here, we only compute the average. We get

\frac{∂F (z, u, v)}{∂v}|_{v=1} = −B(z(1 + u)) + \frac{1}{2z} \frac{\sqrt{1 − 4z} − (1 − 4z)}{\sqrt{1 − 4z(1 + u)}} .  (54)

A standard evaluation of this function gives after division by the normalization factor. Theorem 20. The average number of passes in the model of binary trees is given by

E_{n,p} = \frac{p(n + 1)\binom{2p}{p}4^{n+1−p}}{2(n + 1 − p)\binom{2n}{n}} − \frac{p(2n + 1)}{n + 1 − p} .  (55)

Corollary 21.

E_{n,p} = \frac{2p\binom{2p}{p}}{4^{p}} \sqrt{πn} + O(1) for p fixed ,
E_{n,p} = n + O(1) for l = n − p fixed ,
E_{n,p} = \frac{2\sqrt{ρ}}{1 + \sqrt{ρ}}n + O(1) for p = ρn and 0 < ρ < 1 .

(56)

In the instance of the comparisons we get

F (z, u, v) = z(1 + u)F^{2}(zv, u, v) + v^{−1} + B(z) − v^{−1}B(zv) .  (57)

The equation for the expectations (obtained by differentation w.r.t. v and v = 1) has the solution

G(z, u) = \frac{4}{Y + 1} + \frac{1}{Y^{2}} − \frac{4}{Y} + \frac{4}{Y (X + 1)} − \frac{1}{XY} ,  (58)

with

X = \sqrt{1 − 4z} and Y = \sqrt{1 − 4z(1 + u)} .

After some routine computations we get from that: Theorem 22. The average number of comparisons in the model of binary trees is given by

E_{n,p} = \frac{(n + 1)4^{n}}{\binom{2n}{n}} − \frac{(n + 1)(n + 3p + 1)4^{n−p}}{n + 1 − p} \begin{matrix}( & {2p \atop p} & ) \\ ( & {2n \atop n} & ) \end{matrix} + \frac{2p(2n + 1)}{n + 1 − p} for 1 ≤ p ≤ n .  (59)

Corollary 23.

E_{n,p} = (1 − \frac{\binom{2p}{p}}{4^{p}})\sqrt{π} n^{3/2} + O (\sqrt{n} ) for p fixed ,
E_{n,p} = \sqrt{π} n^{3/2} − 3n + O (\sqrt{n} ) for l = n − p fixed ,
E_{n,p} = \sqrt{π} n^{3/2} − \frac{1 + \sqrt{ρ} + 4ρ}{(1 + \sqrt{ρ})\sqrt{ρ}} n + O (\sqrt{n} ) for fixed ρ = \frac{p}{n} with 0 < ρ < 1 .

(60)

Acknowledgement. We thank Philippe Flajolet who insisted that such an approach should be feasible. As the paper shows, he was right (as usual).

References

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

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

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

[4] P. Kirschenhofer, C. Martínez, and H. Prodinger. Analysis of Hoare’s Find algorithm with median–of–three partition. Random Structures and Algorithms, 10:143–156, 1997.

[5] P. Kirschenhofer and H. Prodinger. Comparisons in Hoare’s Find algorithm. Combinatorics, Probability, and Computing, 1996 (to appear).

[6] 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.

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

[8] 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.

[9] L. Lewin, editor. Structural Properties of Polylogarithms. American Mathematical Society, 1991.

[10] 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.

[11] H. M. Mahmoud and R. T. Smythe. Probabilistic analysis of multiple quickselect. submitted, 1996.

[12] C. Martínez and H. Prodinger. On the number of descendants and ascendants in random search trees. Submitted, 1996.

[13] 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: e9125354@@fbma.tuwien.ac.at (Alois Panholzer)
  E-mail address: Helmut.Prodinger@@tuwien.ac.at
  WWW-address: http://info.tuwien.ac.at/theoinf/proding.htm