%\documentclass[a4paper]{article}
%\usepackage[centertags,reqno]{amstex}

\documentstyle[oldlfont,a4ams,righttag,ctagsplt,emlines2,11pt]{amsart}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\makeatletter
\def\@theoremfont{\it}
\def\slanttheorems{\def\@theoremfont{\sl}}

\def\@begintheorem#1#2[#3]{%
\@theoremfont\trivlist \global\setbox0=\hbox{\bf
 #1}\global\setbox1=\hbox{\bf #2}\item[\hskip \labelsep{\bf #1\ #2.}]}
\let\@opargbegintheorem\relax
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\slanttheorems

\hfuzz=10pt

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}{Proposition}%[section]
\newtheorem{lemma}{Lemma}%[section]
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\theorembodyfont{\slshape}
\newtheorem{ncor}{Corollary}

\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}
\def\comp#1#2{C_{#1,#2}}
\def\compp#1#2{{\cal C}_{#1,#2}(v)}
\def\mom#1#2{D_{#1,#2}}
\def\dilog{\operatorname{dilog}}
\def\var{\operatorname{Var}}
%def\rho{\varrho}


\RequirePackage{theorem}



\newtheorem{rem}{Remark}
\renewcommand{\therem}{}
\newtheorem{nrem}{Remark}

% Acknowledgements
% Entorno para escribir agradecimientos; similar al entorno abstract
% \begin{ackno} We thank Menganito Smith for ... \end{ackno}

\newcommand{\ackno}{\subsection*{\acknoname}}
\newcommand{\acknoname}{Acknowledgement}
\def\endackno{\par}


\begin{document}
\title[Hoare's FIND algorithm]{
Comparisons in Hoare's FIND algorithm}
\author[P.~Kirschenhofer and H.~Prodinger]
{Peter Kirschenhofer and Helmut Prodinger}
\address{  Institut f\"ur Algebra und Diskrete Mathematik\\
Technical University of Vienna\\
Wiedner Hauptstrasse 8--10\\ A-1040 Vienna, Austria.}
\email{Peter.Kirschenhofer@@tuwien.ac.at
{\rm and}  Helmut.Prodinger@@tuwien.ac.at}



\date{\today}
\begin{abstract} 
We study the number of comparisons in Hoare's {\sc Find} algorithm.
Using trivariate generating functions, we get an explicit expression
for the variance of the number of comparisons, if we search for the
$j$th 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. 
\end{abstract} 

\maketitle


\section{Introduction}

The traditional sorting method \textsc{Quicksort} 
\cite{Knuth73, Hoare62} 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.
\begin{figure}[ht]
%\input{qu1.pic}
%TexCad Options
%\grade{\on}
%\emlines{\on}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{1.00}
\special{em:linewidth 0.4pt}
\unitlength 1mm
\linethickness{0.4pt}
\begin{picture}(123.67,97.67)
\put(29.33,12.00){\makebox(0,0)[cc]{1}}
\put(29.33,32.00){\makebox(0,0)[cc]{1}}
\put(29.33,52.00){\makebox(0,0)[cc]{1}}
\put(29.33,72.00){\makebox(0,0)[cc]{1}}
\put(29.33,92.00){\makebox(0,0)[cc]{2}}
\put(39.00,12.00){\makebox(0,0)[cc]{2}}
\put(39.00,32.00){\makebox(0,0)[cc]{2}}
\put(39.00,52.00){\makebox(0,0)[cc]{2}}
\put(39.00,72.00){\makebox(0,0)[cc]{2}}
\put(39.00,92.00){\makebox(0,0)[cc]{1}}
\put(49.00,12.00){\makebox(0,0)[cc]{3}}
\put(49.00,32.00){\makebox(0,0)[cc]{4}}
\put(49.00,52.00){\makebox(0,0)[cc]{5}}
\put(49.00,72.00){\makebox(0,0)[cc]{9}}
\put(49.00,92.00){\makebox(0,0)[cc]{9}}
\put(59.00,12.00){\makebox(0,0)[cc]{4}}
\put(59.00,32.00){\makebox(0,0)[cc]{3}}
\put(59.00,52.00){\makebox(0,0)[cc]{6}}
\put(59.00,72.00){\makebox(0,0)[cc]{6}}
\put(59.00,92.00){\makebox(0,0)[cc]{6}}
\put(69.00,12.00){\makebox(0,0)[cc]{5}}
\put(69.00,32.00){\makebox(0,0)[cc]{5}}
\put(69.00,52.00){\makebox(0,0)[cc]{7}}
\put(69.00,72.00){\makebox(0,0)[cc]{7}}
\put(69.00,92.00){\makebox(0,0)[cc]{7}}
\put(79.00,12.00){\makebox(0,0)[cc]{6}}
\put(79.00,32.00){\makebox(0,0)[cc]{7}}
\put(79.00,52.00){\makebox(0,0)[cc]{3}}
\put(79.00,72.00){\makebox(0,0)[cc]{3}}
\put(79.00,92.00){\makebox(0,0)[cc]{3}}
\put(89.00,12.00){\makebox(0,0)[cc]{7}}
\put(89.00,32.00){\makebox(0,0)[cc]{8}}
\put(89.00,52.00){\makebox(0,0)[cc]{8}}
\put(89.00,72.00){\makebox(0,0)[cc]{8}}
\put(89.00,92.00){\makebox(0,0)[cc]{8}}
\put(99.00,12.00){\makebox(0,0)[cc]{8}}
\put(99.00,32.00){\makebox(0,0)[cc]{6}}
\put(99.00,52.00){\makebox(0,0)[cc]{4}}
\put(99.00,72.00){\makebox(0,0)[cc]{4}}
\put(99.00,92.00){\makebox(0,0)[cc]{4}}
\put(109.00,12.00){\makebox(0,0)[cc]{9}}
\put(109.00,32.00){\makebox(0,0)[cc]{9}}
\put(109.00,52.00){\makebox(0,0)[cc]{9}}
\put(109.00,72.00){\makebox(0,0)[cc]{5}}
\put(109.00,92.00){\makebox(0,0)[cc]{5}}
\put(119.00,12.00){\makebox(0,0)[cc]{10}}
\put(119.00,32.00){\makebox(0,0)[cc]{10}}
\put(119.00,52.00){\makebox(0,0)[cc]{10}}
\put(119.00,72.00){\makebox(0,0)[cc]{10}}
\put(119.00,92.00){\makebox(0,0)[cc]{10}}
\put(116.33,9.33){\framebox(4.67,5.00)[cc]{}}
\put(116.33,29.33){\framebox(4.67,5.00)[cc]{}}
\put(116.33,49.33){\framebox(4.67,5.00)[cc]{}}
\put(96.33,9.33){\framebox(4.67,5.00)[cc]{}}
\put(109.00,12.00){\circle{5.08}}
\put(109.00,32.00){\circle{5.08}}
\put(109.00,52.00){\circle{5.08}}
\put(27.33,9.33){\framebox(4.67,5.00)[cc]{}}
\put(27.33,29.33){\framebox(4.67,5.00)[cc]{}}
\put(27.33,49.33){\framebox(4.67,5.00)[cc]{}}
\put(27.33,69.33){\framebox(4.67,5.00)[cc]{}}
\put(39.00,12.00){\circle{5.08}}
\put(39.00,32.00){\circle{5.08}}
\put(39.00,52.00){\circle{5.08}}
\put(39.00,72.00){\circle{5.08}}
\put(46.33,9.33){\framebox(4.67,5.00)[cc]{}}
\put(76.33,9.33){\framebox(4.67,5.00)[cc]{}}
\put(89.00,12.00){\circle{5.08}}
\put(75.67,8.00){\framebox(26.67,7.33)[cc]{}}
\put(75.67,28.00){\framebox(26.67,7.33)[cc]{}}
\put(69.00,12.00){\circle{5.08}}
\put(69.00,32.00){\circle{5.08}}
\put(59.00,12.00){\circle{5.08}}
\put(45.33,8.00){\framebox(17.67,7.00)[cc]{}}
\put(45.33,28.00){\framebox(17.67,7.00)[cc]{}}
\put(44.67,7.00){\framebox(59.00,9.00)[cc]{}}
\put(44.67,27.00){\framebox(59.00,9.00)[cc]{}}
\put(44.67,47.00){\framebox(59.00,9.00)[cc]{}}
\put(43.67,6.00){\framebox(79.00,11.00)[cc]{}}
\put(43.67,26.00){\framebox(79.00,11.00)[cc]{}}
\put(43.67,46.00){\framebox(79.00,11.00)[cc]{}}
\put(43.67,66.00){\framebox(79.00,11.00)[cc]{}}
\put(26.33,5.00){\framebox(97.33,12.67)[cc]{}}
\put(26.33,25.00){\framebox(97.33,12.67)[cc]{}}
\put(26.33,45.00){\framebox(97.33,12.67)[cc]{}}
\put(26.33,65.00){\framebox(97.33,12.67)[cc]{}}
\put(26.33,85.00){\framebox(97.33,12.67)[cc]{}}
\end{picture}
\caption{The partition process}
\end{figure}

The corresponding binary search tree is depicted in Figure 2.
\begin{figure}[ht]\label{bst}
%\input{bst1.pic}
%TexCad Options
%\grade{\on}
%\emlines{\on}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{0.70}
\special{em:linewidth 0.4pt}
\unitlength 0.70mm
\linethickness{0.4pt}
\begin{picture}(149.23,84.90)
\put(111.33,81.00){\circle{7.80}}
\emline{108.67}{78.00}{1}{96.33}{65.67}{2}
\emline{114.00}{78.00}{3}{126.33}{65.67}{4}
\put(93.33,63.00){\circle{7.80}}
\put(128.33,62.00){\circle{7.80}}
\put(128.33,62.00){\circle{7.80}}
\emline{125.67}{59.00}{5}{113.33}{46.67}{6}
\emline{131.00}{59.00}{7}{143.33}{46.67}{8}
\put(110.33,44.00){\circle{7.80}}
\put(145.33,43.00){\circle{7.80}}
\put(110.33,44.00){\circle{7.80}}
\emline{107.67}{41.00}{9}{95.33}{28.67}{10}
\emline{113.00}{41.00}{11}{125.33}{28.67}{12}
\put(92.33,26.00){\circle{7.80}}
\put(127.33,25.00){\circle{7.80}}
\put(127.33,25.00){\circle{7.80}}
\emline{124.67}{22.00}{13}{112.33}{9.67}{14}
\emline{130.00}{22.00}{15}{142.33}{9.67}{16}
\put(109.33,7.00){\circle{7.80}}
\put(144.33,6.00){\circle{7.80}}
\put(92.33,26.00){\circle{7.80}}
\emline{89.67}{23.00}{17}{77.33}{10.67}{18}
\put(74.33,8.00){\circle{7.80}}
\put(93.33,63.00){\makebox(0,0)[cc]{1}}
\put(111.67,81.00){\makebox(0,0)[cc]{2}}
\put(74.33,7.67){\makebox(0,0)[cc]{3}}
\put(92.33,26.00){\makebox(0,0)[cc]{4}}
\put(110.33,44.00){\makebox(0,0)[cc]{5}}
\put(109.33,6.67){\makebox(0,0)[cc]{6}}
\put(127.33,25.00){\makebox(0,0)[cc]{7}}
\put(144.33,6.00){\makebox(0,0)[cc]{8}}
\put(128.33,62.00){\makebox(0,0)[cc]{9}}
\put(145.33,43.00){\makebox(0,0)[cc]{10}}
\end{picture}
\caption{The corresponding binary search tree with 10 nodes}
\end{figure}

If one only wants the find the $j$th ranked element (which is $j$,
since we assume that the elements in question are $\{1,2,\dots,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
 \textsl{one} subfile.
This procedure is called
Hoare's  \textsc{Find} algorithm \cite{Hoare61}.

There is some renewed interest in Hoare's find algorithm, as can be seen
from the following references, \cite{LeMa95, MaMOSm95, KiMaPr95, Prodinger95}.
For some general background on binary search trees we cite \cite{Mahmoud92};
see also \cite{Hwang90}.


 
Knuth \cite{Knuth72b} has already computed the 
average number  of comparisons $\comp nj$. For this, it is
assumed that every permutation of $\{1,2,\dots,n\}$ is equally
likely, and that the partitioning phase needs $n-1$ comparisons.
Then there is the recursion
\begin{equation}
\comp nj=n-1+\frac{1}{n}\sum_{1\le k <j}\comp{n-k}{j-k}
+\frac{1}{n}\sum_{j< k \le n}\comp{k-1}{j}~.
\end{equation} 
The solution is
\begin{equation}
\comp{n}{j}=
2\Big(n+3+(n+1)H_n-(j+2)H_j-(n+3-j)H_{n+1-j}\Big)~.
\end{equation}
Here, $H_n=\sum_{1\le k\le n}\frac{1}{k}$ is the $n$th 
harmonic number; we will also need  harmonic numbers
of order two, $H_n^{(2)}=\sum_{1\le k\le n}\frac{1}{k^2}$.

More generally, one can also set up an analogous recursion for
the {\sl probability generating functions\/}, viz.
\begin{equation}
\compp nj=\frac{v^{n-1}}{n}\left[\sum_{1\le k <j}\compp{n-k}{j-k}
+1+\sum_{j< k \le n}\compp{k-1}{j}\right]~.
\label{pgf}
\end{equation} 





In this paper we want to compute the \textsl{variance} of the 
number of comparisons.

This requires an incredible amount of computations (by \textsc{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 \cite{Knuth68,GrKnPa89,GrKn82}.









\section{Analysis}

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


The coefficient of $z^nu^jv^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
\begin{equation}\displaystyle{
\frac{z^{10}}{10!}\Big(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}
\Big)}~.
\end{equation}

Recursion (\ref{pgf}) translates into the 
fundamental equation
\begin{equation}
\frac{\partial }{\partial 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}~.
\label{fund:eq}
\end{equation}

We can see this by multiplying the recursion 
(\ref{pgf}) 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
\begin{equation}
F(z;u,1)=\frac{zu}{(1-z)(1-zu)}=\sum_{1\le j\le n}u^jz^n~.
\end{equation}

If we derive the fundamental equation (\ref{fund:eq}) w.r.t. $v$, and 
set $v=1$, we get a differential equation for 
the generating function $G(z,u)$ of the average values
$\comp{n}{j}$, which \textsc{Maple} is able to
solve\footnote{We cannot refrain from mentioning a peculiarity
of \textsc{Maple}. It frequently replaces $\log(1-z)$ 
by \linebreak $\log(z-1)+i\pi$ \&c. To avoid this unpleasant
feature, we had to replace $z$ by $-z$ and
$u$ by $-u$.}, subject to the initial condition $G(0,u)=0$.
It is
\begin{align}\begin{split}
G(z,u)&=\frac{2}{(1-u)(1-z)(1-zu)}\bigg[(u-2)\log\frac{1}{1-zu}+
u(2u-1)\log\frac{1}{1-z}\bigg]\\
&+\frac{2zu(z^2u-2zu+3-2z)}{(1-z)^2(1-zu)^2}~,
\end{split}\end{align}
which gives the coefficients $\comp{n}{j}$. 
(Knuth derived them using an elementary method.) 

If we derive the fundamental equation (\ref{fund:eq}) 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 
$\mom nj$. Its solution is

%\newpage

%\begin{align}\begin{split}
%D(z,u)&=\frac {4 (2-u )^2 }{ (1-z ) (1-zu ) (1-u )^2}
%\log^2 \frac1{1-zu}\\
%&+\frac {4u (1-2u )^2}{ (1-z ) (1-zu ) (1-u )^2}
%\log^2 \frac1{1-z}\\
%&-{\frac {{z}^{2}u (-10{z}^{3}{u}^{2}-5
%{z}^{2}{u}^{2}+6z{u}^{2}-15u-5{z}^{2}u+38zu-15+6z )}
%{ (1-z )^{3} (1-zu )^{3}}}\\
%&+\frac {8u (2-u ) (1-2u )}
%{ (1-z ) (1-zu ) (1-u )^2} 
%\log \frac1{1-zu}\log \frac1{1-u}\\
%&+{\frac { 8(2-u ) (1-2u )}
%{ (1-z ) (1-zu ) (1-u )^{2}}}\log \frac1{1-z}\log \frac1{1-u}\\
%&+{\frac {8u (2-u ) (1-2u )}{ (1-z ) (1-zu ) (1-u )^{2}}}\log \frac1{1-zu}\log(-u)\\
%&-{\frac {2u (-5{z}^{2}u+19{z}^{2}{u}^{2}-11z{u}^{2}-10zu+z+3u+3 )}
%{ (1-u ) (1-z )^{2} (1-zu )^{2}}}\log\frac1{1-z}\\
%&-{\frac { 10{z}^{2}{u}^{2}-38{z}^{2}u-2z{u}^{2}+20zu+22z-6u-6 }
%{ (1-u ) (1-z )^{2} (1-zu )^{2}}}\log\frac1{1-zu}\\
%&- \frac{8u(2-u ) (1-2u )}
%{(1-z ) (1-zu )(1-u )^{2}}
% \bigg({\dilog}\Big(-{\frac { (1-z )u}{1-u}}\Big)
%-{\dilog}\Big(-{\frac {u}{1-u}}\Big)\bigg)\\
%&- \frac{8(2-u ) (1-2u )}
%{(1-z ) (1-zu )(1-u )^{2}}\bigg(
% {\dilog}\Big({\frac {1-zu}{1-u}}\Big)-{\dilog}\Big(\frac1{1-u} \Big) \bigg) ~.
%\end{split}\end{align}
%

\begin{align}\begin{split}
D(z,u)&=\frac {4 (2-u )^2 }{ (1-z ) (1-zu ) (1-u )^2}
\log^2 \frac1{1-zu}\\
&+\frac {4u (1-2u )^2}{ (1-z ) (1-zu ) (1-u )^2}
\log^2 \frac1{1-z}\\
&-{\frac {{z}^{2}u (-10{z}^{3}{u}^{2}-5
{z}^{2}{u}^{2}+6z{u}^{2}-15u-5{z}^{2}u+38zu-15+6z )}
{ (1-z )^{3} (1-zu )^{3}}}+\quad\text{\scriptsize{\textsf{$ \rightarrow$ next page}}}
\end{split}\end{align}

\begin{align*}
\phantom{D(z,u)}
&+\frac {8u (2-u ) (1-2u )}
{ (1-z ) (1-zu ) (1-u )^2} 
\log \frac1{1-zu}\log \frac1{1-u}\\
&+{\frac { 8(2-u ) (1-2u )}
{ (1-z ) (1-zu ) (1-u )^{2}}}\log \frac1{1-z}\log \frac1{1-u}\\
&+{\frac {8u (2-u ) (1-2u )}{ (1-z ) (1-zu ) (1-u )^{2}}}\log \frac1{1-zu}\log(-u)\\
&-{\frac {2u (-5{z}^{2}u+19{z}^{2}{u}^{2}-11z{u}^{2}-10zu+z+3u+3 )}
{ (1-u ) (1-z )^{2} (1-zu )^{2}}}\log\frac1{1-z}\\
&-{\frac { 10{z}^{2}{u}^{2}-38{z}^{2}u-2z{u}^{2}+20zu+22z-6u-6 }
{ (1-u ) (1-z )^{2} (1-zu )^{2}}}\log\frac1{1-zu}\\
&- \frac{8u(2-u ) (1-2u )}
{(1-z ) (1-zu )(1-u )^{2}}
 \bigg({\dilog}\Big(-{\frac { (1-z )u}{1-u}}\Big)
-{\dilog}\Big(-{\frac {u}{1-u}}\Big)\bigg)\\
&- \frac{8(2-u ) (1-2u )}
{(1-z ) (1-zu )(1-u )^{2}}\bigg(
 {\dilog}\Big({\frac {1-zu}{1-u}}\Big)-{\dilog}\Big(\frac1{1-u} \Big) \bigg) ~.
\end{align*}

Let us recall the definition of the dilogarithm \cite{AbSt73},
\begin{equation}
\dilog z=\int_1^z\frac{\log t}{1-t}\, dt~.
\end{equation}

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 \textsc{Maple}),

%\newpage


%\begin{align}\begin{split}\label{G:zerlegt}
%D(z,u)&=\frac{9}{(1-z)^3}\ \sum_{j\ge1}u^j\\
%&+\log^2\frac1{1-z}\ \sum_{j\ge1}u^j
%\bigg\{
%\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}\bigg\}\\
%&+\frac{1}{(1-z)^2}\ \sum_{j\ge1}u^j\bigg\{-8(j+2)H_j+21j-25\bigg\}\\
%&+\frac{1}{(1-z)^2}\log\frac1{1-z}\sum_{j\ge2}u^j
%\bigg\{(8j-16H_{j-1}-26)z^j\\
%&\qquad\qquad\qquad\qquad\qquad\qquad
%+\Big(-16j+70+24H_{j-1}-\frac{8}{j-1}\Big)z^{j-1}\\
%&\qquad\qquad\qquad\qquad\qquad\qquad
%+\sum_{i=2}^{j-1}\Big(8H_{j-i}-\frac{8i}{j-i}+16
%-\frac{16}{i+1}+\frac{40}{i}-\frac{16}{i-1}\Big)z^{j-i}\\ 
%& \qquad\qquad\qquad\qquad\qquad\qquad
%+\Big(-8H_j+\frac{24}{j}-12-\frac{16}{j-1}\Big)
%\bigg\}\\
%&+\frac{1}{(1-z)^2}\log\frac1{1-z}\cdot u (10-18z) \\
%&+\frac1{1-z}\ \sum_{j\ge1}u^j\bigg\{
%(2j^2+18j+16)H_j^2+\Big(-6j^2-14j+14-\frac{16}{j}\Big)H_j\\
%&\qquad\qquad\qquad\qquad-(2j^2+10j+16)H_j^{(2)}
%-2j^2+25j+10\bigg\}~.
%\end{split}
%\end{align}
%

\begin{align}\begin{split}\label{G:zerlegt}
D(z,u)&=\frac{9}{(1-z)^3}\ \sum_{j\ge1}u^j\\
&+\log^2\frac1{1-z}\ \sum_{j\ge1}u^j
\bigg\{
\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}\bigg\}\\
&+\frac{1}{(1-z)^2}\ \sum_{j\ge1}u^j\bigg\{-8(j+2)H_j+21j-25\bigg\}\\
&+\frac{1}{(1-z)^2}\log\frac1{1-z}\sum_{j\ge2}u^j
\bigg\{(8j-16H_{j-1}-26)z^j\\
&\qquad\qquad\qquad\qquad\qquad\qquad
+\Big(-16j+70+24H_{j-1}-\frac{8}{j-1}\Big)z^{j-1}\\
&\qquad\qquad\qquad\qquad\qquad\qquad
+\sum_{i=2}^{j-1}\Big(8H_{j-i}-\frac{8i}{j-i}+16
-\frac{16}{i+1}+\frac{40}{i}-\frac{16}{i-1}\Big)z^{j-i}\\ 
& \qquad\qquad\qquad\qquad\qquad\qquad
+\Big(-8H_j+\frac{24}{j}-12-\frac{16}{j-1}\Big)
\bigg\}\\
&+\frac{1}{(1-z)^2}\log\frac1{1-z}\cdot u (10-18z) +
\quad\text{\scriptsize{\textsf{$ \rightarrow$ next page}}}
\end{split}
\end{align}

\newpage




\begin{align*}
\phantom{D(z,u)}&+\frac1{1-z}\ \sum_{j\ge1}u^j\bigg\{
(2j^2+18j+16)H_j^2+\Big(-6j^2-14j+14-\frac{16}{j}\Big)H_j\\
&\qquad\qquad\qquad\qquad-(2j^2+10j+16)H_j^{(2)}
-2j^2+25j+10\bigg\}~.
\end{align*}














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

\begin{gather}
\begin{split}
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}~.
\end{split}
\end{gather}
Reading of the coefficient of $u^j$ is pretty much 
standard except for the following
\begin{equation}
[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~.
\end{equation}
For this one we argue as follows. Since
\begin{equation}
\frac{d}{du}\dilog\frac{1}{1-u}=\left(
-\frac{1}{1-u}-\frac{1}{u}
\right)\log\frac{1}{1-u}~,
\end{equation}
we find
\begin{equation}
[u^j]\dilog\frac{1}{1-u}=-\frac{1}{j}\left(H_{j-1}+\frac1j\right)
\end{equation}
The convolution, caused by the factor $\frac{1}{(1-u)^2}$, is then
handled by formul\ae\ in \cite{Knuth68}.

Now we read of the coefficient of $u^jz^n$ in $D(z,u)$, as shown in
(\ref{G:zerlegt}). Using all kind of identities for harmonic numbers
(see \cite{Knuth68}) we get as an intermediary result


%\newpage

%\begin{align}
%\begin{split}
%\mom nj&=-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\\
%&+\Big(-4j^2+(12+8n)j-4n^2+8-12n\Big)\,H_jH_{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\\
%&+\Big(2j^2+(-4n-18)j+2n^2+18n+32\Big)\,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)}\\
%&+\Big(-2n^2+4nj-18n-2j^2-32+18j\Big)\,H_{n+1-j}^{(2)}\\ 
%&+\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)\sum_{k=1}^j\frac{H_{n-k}}{k}
%+8(n+1-j)\sum_{k=1}^j\frac{H_{n+k-j}}{k}~.
%\end{split}
%\end{align}
%

\begin{align}
\begin{split}
\mom nj&=-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\\
&+\Big(-4j^2+(12+8n)j-4n^2+8-12n\Big)\,H_jH_{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\\
&+\Big(2j^2+(-4n-18)j+2n^2+18n+32\Big)\,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)}\\
&+\Big(-2n^2+4nj-18n-2j^2-32+18j\Big)\,H_{n+1-j}^{(2)}+
\quad\text{\scriptsize{\textsf{$ \rightarrow$ next page}}}
\end{split}
\end{align}

\begin{align*}
\phantom{\mom nj}&+\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)\sum_{k=1}^j\frac{H_{n-k}}{k}
+8(n+1-j)\sum_{k=1}^j\frac{H_{n+k-j}}{k}~.
\end{align*}



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

\begin{equation}
\sum_{k=1}^j\frac{H_{n-k}}{k}+\sum_{k=1}^{n+1-j}\frac{H_{n-k}}{k}
=H_jH_{n+1-j}+H_n^2-H_n^{(2)}-\frac1{j(n+1-j)}
\end{equation}
\end{lemma}

\begin{lemma}{\rm [Reciprocity law]}
\begin{align}
\begin{split}
\sum_{k=1}^j\frac{H_{n+k-j}}{k}+
\sum_{k=1}^{n+1-j}\frac{H_{j+k-1}}{k}
&=\frac12\Big(H_{j}^2+H_j^{(2)}\Big)+\frac12\Big(H_{n+1-j}^2+H_{n+1-j}^{(2)}\Big)\\
&+H_jH_{n+1-j}+\frac1{j(n+1-j)}\\
&+\frac{n+1}{j(n+1-j)}\Big(H_n-H_j-H_{n+1-j}\Big)~.
\end{split}
\end{align}
\end{lemma}

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

%\newpage

\begin{lemma}
\begin{align}
\begin{split}
\sum_{k=1}^j\frac{H_{n-k}}{k}+
\sum_{k=1}^j\frac{H_{n+k-j}}{k}&
=\frac1{n+1-j}\Big(H_n-H_j-H_{n+1-j}\Big)
+H_jH_n+H_jH_{n+1-j}\\
&-H_nH_{n+1-j}+\frac12\Big(H_n^2-H_{n}^{(2)}\Big)+\frac12\Big(H_{n+1-j}^2+H_{n+1-j}^{(2)}\Big)
\end{split}
\end{align}
\end{lemma}
All three lemmata can be easily proved by setting up bivariate generating functions on
both sides. The formul\ae\ are `nice' and easier to \textsl{prove}
 than to \textsl{find.} As an example, we give the proof of Lemma~1.
In terms of generating functions we have to prove that
\begin{align}\begin{split}
&\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}~,
\end{split}\end{align}
which is easily seen to be true.

Using the  lemmata, we can do the following,

\begin{align}
\begin{split}
(n+1-2j)\sum_{k=1}^j\frac{H_{n-k}}{k}
&=(n+1-j)\sum_{k=1}^j\frac{H_{n-k}}{k}+j\sum_{k=1}^{n+1-j}\frac{H_{n-k}}{k}\\
&-j\bigg(H_jH_{n+1-j}+H_n^2-H_n^{(2)}-\frac1{j(n+1-j)}\bigg)~.
\end{split}
\end{align}
This gives us the final result on the second factorial moments.

%\newpage

\bigskip

\begin{proposition}
\begin{align}
\begin{split}
\mom nj&= -2(n+1)(n+6)\, H_n^2\\
&-8H_n\Big(jH_j+(n+1-j)\,H_{n+1-j}\Big)\\
&+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\Big(-j^2+(n+1)j-n^2-n+4\Big)H_{j}\,H_{n+1-j}\\
&-\frac{2}{j(n+1-j)}\Big(-2(3n+7)j^3
	+(6n^2+14n+13)j^2+(n+1)(6n+1)j+8(n+1)\Big)\,H_j\\
&-\frac{2}{j(n+1-j)}\Big(2(3n+7)j^3-(12n^2+46n+29)j^2\\
&\qquad\qquad\qquad\qquad\qquad\qquad+(n+1)(6n^2+26n+15)j+8(n+1)\Big)\,
 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\bigg((n+1-j)\sum_{k=1}^j\frac{H_{n-k}}{k}+
j\sum_{k=1}^{n+1-j}\frac{H_{n-k}}{k}    \bigg)~.\qquad\qed
\end{split}
\end{align}
\end{proposition}

%\newpage
\medskip\noindent
Computing $\var_{n,j}=\mom nj+\comp nj-({\comp nj})^2$, we find the 
variance.
%\newpage

\medskip

\begin{theorem} The variance of the number of comparisons needed to find the
$j$th element out of $n$ elements is given by the exact formula

%\begin{align}
%\begin{split}
%\var_{ n,j}&= -2(n+1)(3n+8) \,H_n^2\\
%&+8\,H_n\,H_j\Big(n(j+2)+2      \Big)
%        +8\,H_n\,H_{n+1-j}\Big(n(n+3-j)+2      \Big)                    \\
%&+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\Big(j^2-(n+1)j-n^2-5n-8\Big)\,H_{j}\,H_{n+1-j}\\
%&-\frac{2}{j(n+1-j)}\Big(-(2n+3)j^3+(2n^2+7n+24)j^2
%       -(n+1)(2n+21)j+8(n+1)\Big)\,H_j\\
%&-\frac{2}{j(n+1-j)}\Big((2n+3)j^3-(4n^2+8n-15)j^2\\
%&\qquad\qquad\qquad\qquad\qquad\qquad+(n+1)(2n^2+3n-18)j+8(n+1)\Big)
%\, 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\bigg((n+1-j)\sum_{k=1}^j\frac{H_{n-k}}{k}+
%j\sum_{k=1}^{n+1-j}\frac{H_{n-k}}{k}   \bigg)~.\qquad\qed
%\end{split}
%\end{align}
%

\begin{align}
\begin{split}
\var_{ n,j}&= -2(n+1)(3n+8) \,H_n^2\\
&+8\,H_n\,H_j\Big(n(j+2)+2      \Big)
	 +8\,H_n\,H_{n+1-j}\Big(n(n+3-j)+2      \Big)                    \\
&+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\Big(j^2-(n+1)j-n^2-5n-8\Big)\,H_{j}\,H_{n+1-j}+
\quad\text{\scriptsize{\textsf{$ \rightarrow$ next page}}}
\end{split}
\end{align}

\begin{align*}
\phantom{\var_{ n,j}}
&-\frac{2}{j(n+1-j)}\Big(-(2n+3)j^3+(2n^2+7n+24)j^2
	-(n+1)(2n+21)j+8(n+1)\Big)\,H_j\\
&-\frac{2}{j(n+1-j)}\Big((2n+3)j^3-(4n^2+8n-15)j^2\\
&\qquad\qquad\qquad\qquad\qquad\qquad+(n+1)(2n^2+3n-18)j+8(n+1)\Big)
\, 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\bigg((n+1-j)\sum_{k=1}^j\frac{H_{n-k}}{k}+
j\sum_{k=1}^{n+1-j}\frac{H_{n-k}}{k}    \bigg)~.\qquad\qed
\end{align*}



\end{theorem}

In the instance $n=2N+1$, $j=N+1$ (searching for the
\textsl{median}), we can use the first reciprocity law
to simplify the variance. We get
\begin{align}\begin{split}
\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{split}\end{align}

Asymptotically we get from this
\begin{equation}
\var_{2N+1,N+1}\sim N^2\Big(16\log2-16\log^22-\tfrac{2}{3}\pi^2+7\Big)~.
\end{equation}
The numerical constant is $3.823370396$ .

To get a better feeling about the sums $\sum_{k=1}^j\frac{H_{n-k}}{k}$, 
we compute their {\sl average\/}
\begin{equation}
\frac{1}{n}\sum_{1\le j \le n} \sum_{k=1}^j\frac{H_{n-k}}{k}
=\frac{n+1}{n}\left(H_n^2-H_n^{(2)}\right)-H_n+1~.
\end{equation}
It might be even more instructive to compute the average value
\begin{align}\begin{split}
\frac{1}{n}\sum_{1\le j \le n} &\left[
(n+1-j)\sum_{k=1}^j\frac{H_{n-k}}{k}+
j\sum_{k=1}^{n+1-j}\frac{H_{n-k}}{k}
\right]\\
&\qquad=\frac{(n+2)(n+1)}{n}\left(H_n^2-H_n^{(2)}\right)
-\frac{3n+5}{2}\, H_n+\frac{5n+11}{4}~.
\end{split}\end{align}

Now we want to study the asymptotic behaviour of the variance, if $n\to\infty$ and
$j=\rho n$, $0<\rho<1$.

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


\begin{lemma}  
As $n\to\infty$ and $j=\rho n$ with $0<\rho<1$, we have
\begin{equation} 
\sum_{k=1}^j\frac{H_{n-k}}{k}=
\log^2n+(2\gamma+\log\rho)\log n+\big(\gamma^2+\gamma\log\rho-\dilog(1-\rho)\big)+{ o}(1)~.
\end{equation}
\end{lemma}

Using this intermediary result in our formula for the variance, an elementary calculation
gives us the asymptotic evaluation of the variance.

\begin{theorem} The variance of the number of comparisons in Hoare's {\sc Find}
algorithm to find the $\rho n$--th out of $n$ elements $(0<\rho<1)$  fulfills for
$n\to\infty$ 


\begin{align}
\begin{split}
\var_{ n,\rho n}\sim n^2\, \Big( &-2\rho^2\log^2\rho+4(\rho^2-\rho-1)\log\rho\log(1-\rho)
-2(1-\rho)^2\log^2(1-\rho)\\
&-4\rho\log\rho-4(1-\rho)\log(1-\rho)
-4\rho\dilog\rho-4(1-\rho)\dilog(1-\rho)\\
&+\tfrac{2}{3}\pi^2\rho(1-\rho)+5\rho(1-\rho)+\tfrac12\Big)~.\qquad\qed
\end{split}\end{align}

\end{theorem}

\begin{figure}[ht]
%\input{1.tex}
% GNUPLOT: LaTeX picture with emtex specials
\setlength{\unitlength}{0.240900pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\special{em:linewidth 0.4pt}%
\begin{picture}(1200,720)(-280,0)
\font\gnuplot=cmr10 at 10pt
\gnuplot
\put(176,68){\special{em:moveto}}
\put(176,697){\special{em:lineto}}
\put(176,68){\special{em:moveto}}
\put(156,68){\special{em:lineto}}
\put(154,68){\makebox(0,0)[r]{$0.5$}}
\put(176,131){\special{em:moveto}}
\put(156,131){\special{em:lineto}}
\put(154,131){\makebox(0,0)[r]{$0.55$}}
\put(176,194){\special{em:moveto}}
\put(156,194){\special{em:lineto}}
\put(154,194){\makebox(0,0)[r]{$0.6$}}
\put(176,257){\special{em:moveto}}
\put(156,257){\special{em:lineto}}
\put(154,257){\makebox(0,0)[r]{$0.65$}}
\put(176,320){\special{em:moveto}}
\put(156,320){\special{em:lineto}}
\put(154,320){\makebox(0,0)[r]{$0.7$}}
\put(176,383){\special{em:moveto}}
\put(156,383){\special{em:lineto}}
\put(154,383){\makebox(0,0)[r]{$0.75$}}
\put(176,445){\special{em:moveto}}
\put(156,445){\special{em:lineto}}
\put(154,445){\makebox(0,0)[r]{$0.8$}}
\put(176,508){\special{em:moveto}}
\put(156,508){\special{em:lineto}}
\put(154,508){\makebox(0,0)[r]{$0.85$}}
\put(176,571){\special{em:moveto}}
\put(156,571){\special{em:lineto}}
\put(154,571){\makebox(0,0)[r]{$0.9$}}
\put(176,634){\special{em:moveto}}
\put(156,634){\special{em:lineto}}
\put(154,634){\makebox(0,0)[r]{$0.95$}}
\put(176,697){\special{em:moveto}}
\put(156,697){\special{em:lineto}}
\put(154,697){\makebox(0,0)[r]{$1$}}
\put(176,68){\special{em:moveto}}
\put(176,48){\special{em:lineto}}
\put(176,23){\makebox(0,0){$0$}}
\put(368,68){\special{em:moveto}}
\put(368,48){\special{em:lineto}}
\put(368,23){\makebox(0,0){$0.2$}}
\put(560,68){\special{em:moveto}}
\put(560,48){\special{em:lineto}}
\put(560,23){\makebox(0,0){$0.4$}}
\put(752,68){\special{em:moveto}}
\put(752,48){\special{em:lineto}}
\put(752,23){\makebox(0,0){$0.6$}}
\put(944,68){\special{em:moveto}}
\put(944,48){\special{em:lineto}}
\put(944,23){\makebox(0,0){$0.8$}}
\put(1136,68){\special{em:moveto}}
\put(1136,48){\special{em:lineto}}
\put(1136,23){\makebox(0,0){$1$}}
\put(176,68){\special{em:moveto}}
\put(186,123){\special{em:lineto}}
\put(195,170){\special{em:lineto}}
\put(205,212){\special{em:lineto}}
\put(214,249){\special{em:lineto}}
\put(224,282){\special{em:lineto}}
\put(234,312){\special{em:lineto}}
\put(243,340){\special{em:lineto}}
\put(253,365){\special{em:lineto}}
\put(262,388){\special{em:lineto}}
\put(272,409){\special{em:lineto}}
\put(282,429){\special{em:lineto}}
\put(291,447){\special{em:lineto}}
\put(301,464){\special{em:lineto}}
\put(310,479){\special{em:lineto}}
\put(320,493){\special{em:lineto}}
\put(330,506){\special{em:lineto}}
\put(339,518){\special{em:lineto}}
\put(349,529){\special{em:lineto}}
\put(358,539){\special{em:lineto}}
\put(368,549){\special{em:lineto}}
\put(378,557){\special{em:lineto}}
\put(387,565){\special{em:lineto}}
\put(397,573){\special{em:lineto}}
\put(406,579){\special{em:lineto}}
\put(416,586){\special{em:lineto}}
\put(426,591){\special{em:lineto}}
\put(435,597){\special{em:lineto}}
\put(445,601){\special{em:lineto}}
\put(454,606){\special{em:lineto}}
\put(464,610){\special{em:lineto}}
\put(474,614){\special{em:lineto}}
\put(483,617){\special{em:lineto}}
\put(493,620){\special{em:lineto}}
\put(502,623){\special{em:lineto}}
\put(512,625){\special{em:lineto}}
\put(522,628){\special{em:lineto}}
\put(531,630){\special{em:lineto}}
\put(541,632){\special{em:lineto}}
\put(550,633){\special{em:lineto}}
\put(560,635){\special{em:lineto}}
\put(570,636){\special{em:lineto}}
\put(579,637){\special{em:lineto}}
\put(589,638){\special{em:lineto}}
\put(598,639){\special{em:lineto}}
\put(608,640){\special{em:lineto}}
\put(618,640){\special{em:lineto}}
\put(627,641){\special{em:lineto}}
\put(637,641){\special{em:lineto}}
\put(646,641){\special{em:lineto}}
\put(656,641){\special{em:lineto}}
\put(666,641){\special{em:lineto}}
\put(675,641){\special{em:lineto}}
\put(685,641){\special{em:lineto}}
\put(694,640){\special{em:lineto}}
\put(704,640){\special{em:lineto}}
\put(714,639){\special{em:lineto}}
\put(723,638){\special{em:lineto}}
\put(733,637){\special{em:lineto}}
\put(742,636){\special{em:lineto}}
\put(752,635){\special{em:lineto}}
\put(762,633){\special{em:lineto}}
\put(771,632){\special{em:lineto}}
\put(781,630){\special{em:lineto}}
\put(790,628){\special{em:lineto}}
\put(800,625){\special{em:lineto}}
\put(810,623){\special{em:lineto}}
\put(819,620){\special{em:lineto}}
\put(829,617){\special{em:lineto}}
\put(838,614){\special{em:lineto}}
\put(848,610){\special{em:lineto}}
\put(858,606){\special{em:lineto}}
\put(867,601){\special{em:lineto}}
\put(877,597){\special{em:lineto}}
\put(886,591){\special{em:lineto}}
\put(896,586){\special{em:lineto}}
\put(906,579){\special{em:lineto}}
\put(915,573){\special{em:lineto}}
\put(925,565){\special{em:lineto}}
\put(934,557){\special{em:lineto}}
\put(944,549){\special{em:lineto}}
\put(954,539){\special{em:lineto}}
\put(963,529){\special{em:lineto}}
\put(973,518){\special{em:lineto}}
\put(982,506){\special{em:lineto}}
\put(992,493){\special{em:lineto}}
\put(1002,479){\special{em:lineto}}
\put(1011,464){\special{em:lineto}}
\put(1021,447){\special{em:lineto}}
\put(1030,429){\special{em:lineto}}
\put(1040,409){\special{em:lineto}}
\put(1050,388){\special{em:lineto}}
\put(1059,365){\special{em:lineto}}
\put(1069,340){\special{em:lineto}}
\put(1078,312){\special{em:lineto}}
\put(1088,282){\special{em:lineto}}
\put(1098,249){\special{em:lineto}}
\put(1107,212){\special{em:lineto}}
\put(1117,170){\special{em:lineto}}
\put(1126,123){\special{em:lineto}}
\put(1136,68){\special{em:lineto}}
\put(176,68){\special{em:moveto}}
\put(186,68){\special{em:lineto}}
\put(195,68){\special{em:lineto}}
\put(205,68){\special{em:lineto}}
\put(215,68){\special{em:lineto}}
\put(224,68){\special{em:lineto}}
\put(234,68){\special{em:lineto}}
\put(244,68){\special{em:lineto}}
\put(254,68){\special{em:lineto}}
\put(263,68){\special{em:lineto}}
\put(273,68){\special{em:lineto}}
\put(283,68){\special{em:lineto}}
\put(292,68){\special{em:lineto}}
\put(302,68){\special{em:lineto}}
\put(312,68){\special{em:lineto}}
\put(321,68){\special{em:lineto}}
\put(331,68){\special{em:lineto}}
\put(341,68){\special{em:lineto}}
\put(351,68){\special{em:lineto}}
\put(360,68){\special{em:lineto}}
\put(370,68){\special{em:lineto}}
\put(380,68){\special{em:lineto}}
\put(389,68){\special{em:lineto}}
\put(399,68){\special{em:lineto}}
\put(409,68){\special{em:lineto}}
\put(418,68){\special{em:lineto}}
\put(428,68){\special{em:lineto}}
\put(438,68){\special{em:lineto}}
\put(448,68){\special{em:lineto}}
\put(457,68){\special{em:lineto}}
\put(467,68){\special{em:lineto}}
\put(477,68){\special{em:lineto}}
\put(486,68){\special{em:lineto}}
\put(496,68){\special{em:lineto}}
\put(506,68){\special{em:lineto}}
\put(515,68){\special{em:lineto}}
\put(525,68){\special{em:lineto}}
\put(535,68){\special{em:lineto}}
\put(544,68){\special{em:lineto}}
\put(554,68){\special{em:lineto}}
\put(564,68){\special{em:lineto}}
\put(574,68){\special{em:lineto}}
\put(583,68){\special{em:lineto}}
\put(593,68){\special{em:lineto}}
\put(603,68){\special{em:lineto}}
\put(612,68){\special{em:lineto}}
\put(622,68){\special{em:lineto}}
\put(632,68){\special{em:lineto}}
\put(641,68){\special{em:lineto}}
\put(651,68){\special{em:lineto}}
\put(661,68){\special{em:lineto}}
\put(671,68){\special{em:lineto}}
\put(680,68){\special{em:lineto}}
\put(690,68){\special{em:lineto}}
\put(700,68){\special{em:lineto}}
\put(709,68){\special{em:lineto}}
\put(719,68){\special{em:lineto}}
\put(729,68){\special{em:lineto}}
\put(738,68){\special{em:lineto}}
\put(748,68){\special{em:lineto}}
\put(758,68){\special{em:lineto}}
\put(768,68){\special{em:lineto}}
\put(777,68){\special{em:lineto}}
\put(787,68){\special{em:lineto}}
\put(797,68){\special{em:lineto}}
\put(806,68){\special{em:lineto}}
\put(816,68){\special{em:lineto}}
\put(826,68){\special{em:lineto}}
\put(835,68){\special{em:lineto}}
\put(845,68){\special{em:lineto}}
\put(855,68){\special{em:lineto}}
\put(864,68){\special{em:lineto}}
\put(874,68){\special{em:lineto}}
\put(884,68){\special{em:lineto}}
\put(894,68){\special{em:lineto}}
\put(903,68){\special{em:lineto}}
\put(913,68){\special{em:lineto}}
\put(923,68){\special{em:lineto}}
\put(932,68){\special{em:lineto}}
\put(942,68){\special{em:lineto}}
\put(952,68){\special{em:lineto}}
\put(961,68){\special{em:lineto}}
\put(971,68){\special{em:lineto}}
\put(981,68){\special{em:lineto}}
\put(991,68){\special{em:lineto}}
\put(1000,68){\special{em:lineto}}
\put(1010,68){\special{em:lineto}}
\put(1020,68){\special{em:lineto}}
\put(1029,68){\special{em:lineto}}
\put(1039,68){\special{em:lineto}}
\put(1049,68){\special{em:lineto}}
\put(1058,68){\special{em:lineto}}
\put(1068,68){\special{em:lineto}}
\put(1078,68){\special{em:lineto}}
\put(1088,68){\special{em:lineto}}
\put(1097,68){\special{em:lineto}}
\put(1107,68){\special{em:lineto}}
\put(1117,68){\special{em:lineto}}
\put(1126,68){\special{em:lineto}}
\put(1136,68){\special{em:lineto}}
\end{picture}
\caption{The coefficient of $n^2$ in Theorem 2, as a function of $\rho$ }
\end{figure}


\section{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.
\smallskip

We have the 
fundamental equation
\begin{equation}\label{passes:eq}
\frac{\partial }{\partial 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}
\end{equation}
The equation can easily be gained from referring to (\ref{fund:eq}):
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\to zv$  on the right-hand-side
of (\ref{fund:eq}) we find (\ref{passes:eq}).




The expectation is an old result of Arora and Dent \cite{ArDe69};
\begin{equation}
E_{n,j}=H_{j}+H_{n+1-j}-1~.
\end{equation}
For the variance we get
\begin{align}\begin{split}
\var_{n,j}&=\frac{2(n+1)}{j(n+1-j)}\,H_n
+\left(1-\frac{2(n+1)}{j(n+1-j)}\right)\big(H_j+H_{n+1-j}\big)\\
&-\left(H_j^{(2)}+H_{n+1-j}^{(2)}\right)
+\frac{2}{j(n+1-j)}+2~.
\end{split}\end{align}

\begin{ackno}
One of us (H.~P.) had the opportunity to use the powerful computers at \textsc{Inria}.
Thanks are due to P.~Flajolet for the generous invitation.
\end{ackno}


\bibliographystyle{plain} 


%\bibliography{pro_bib}

\begin{thebibliography}{10}

\bibitem{AbSt73}
M.~Abramowitz and I.~A. Stegun.
\newblock {\em Handbook of Mathematical Functions}.
\newblock Dover, 1973.
\newblock A reprint of the tenth National Bureau of Standards edition, 1964.

\bibitem{ArDe69}
S.~Arora and W.~Dent.
\newblock Randomized binary search technique.
\newblock {\em Communications of the ACM}, 12:77--80, 1969.

\bibitem{GrKnPa89}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics}.
\newblock Addison Wesley, 1989.

\bibitem{GrKn82}
D.~H. Greene and D.~E. Knuth.
\newblock {\em Mathematics for the analysis of algorithms}.
\newblock Birkhauser, Boston, second edition, 1982.

\bibitem{Hoare61}
C.~A.~R. Hoare.
\newblock Find ({A}lgorithm 65).
\newblock {\em Communications of the ACM}, 4:321--322, 1961.

\bibitem{Hoare62}
C.~A.~R. Hoare.
\newblock Quicksort.
\newblock {\em Computer Journal}, 5:10--15, 1962.

\bibitem{Hwang90}
H.-K. Hwang.
\newblock On the average shape of binary search trees.
\newblock {\em Unpublished manuscript}, 1990.

\bibitem{KiMaPr95}
P.~Kirschenhofer, C.~Mart\'{\i}nez, and H.~{P}rodinger.
\newblock Analysis of {H}oare's {F}ind algorithm with median--of--three
  partition.
\newblock {\em Submitted}, 1995.

\bibitem{Knuth68}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 1: Fundamental
  Algorithms.
\newblock Addison-Wesley, 1968.
\newblock Second edition, 1973.

\bibitem{Knuth72b}
D.~E. Knuth.
\newblock Mathematical analysis of algorithms.
\newblock In {\em Information Processing 71}, pages 19--27. North Holland
  Publishing Company, 1972.
\newblock Proceedings of IFIP Congress, Ljubljana, 1971.

\bibitem{Knuth73}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 3: Sorting and
  Searching.
\newblock Addison-Wesley, 1973.

\bibitem{LeMa95}
J.~Lent and H.~M. Mahmoud.
\newblock Average--case analysis of multiple quickselect: An algorithm for
  finding order statistics.
\newblock {\em Statistics and Probability Letters (to appear)}.

\bibitem{Mahmoud92}
H.~M. Mahmoud.
\newblock {\em Evolution of Random Search Trees}.
\newblock John Wiley, New York, 1992.

\bibitem{MaMOSm95}
H.~M. Mahmoud, R.~M. Modarres, and R.~T. Smythe.
\newblock Analysis of one-sided quicksort: An algorithm for order statistics.
\newblock {\em RAIRO, Theoretical Informatics and Applications}, 29:255--276,
  1995.

\bibitem{Prodinger95}
H.~Prodinger.
\newblock Multiple quickselect --- {H}oare's find algorithm for several
  elements.
\newblock {\em Information Processing Letters}, 56:123--129, 1995.

\end{thebibliography}





\end{document}












