%Siam J. on Computing


\input amstex
\documentstyle{amsppt}

\hsize =13.0 cm
\vsize=18.5 cm
\NoBlackBoxes

\topmatter
%\nologo

\redefine\L{\log 2}
\title NOTE\\ \\
       EXTERNAL INTERNAL NODES IN \\
       DIGITAL SEARCH TREES\\
       VIA MELLIN TRANSFORMS
\endtitle

\author Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address TU Vienna
\newline Wiedner Hauptstra{\ss}e 8-10
\newline A-1040 Vienna
\newline Austria 
\endaddress

\endtopmatter

\document

\bigskip
\rightline{{\it January 13, 1992}}
\bigskip

Knuth \cite {4; {\rm ex.6.3.29}} posed it as an open problem 
(ranked $M46$) to compute (asymptotically)
$l_N$, the average number of external internal nodes in a random 
{\it digital search tree} built by $N$ data.

This problem was settled by Flajolet and Sedgewick \cite 2 by a very
convenient technique, called {\it Rice's method}. This method has some
advantages over the {\it Mellin transform technique} that Knuth used heavily
in his famous book. (In passing it will be mentioned that the
variance was treated by P. Kirschenhofer and the author \cite 3.)

In this note we show that 
{\it Knuth could have given a solution himself},
because in the present approach we follow his ideas that he used in a 
similar (although easier) problem (cf. \cite{4; {\rm p.497}}).

For a complete description of the problem and digital search trees we must
refer to \cite 4 and \cite 2 in order to keep this note short.
For the use of the Mellin transform technique we cite \cite 1.

\bigskip

The problem is to compute
$$
l_N=N-\sum_{k=2}^N\binom Nk(-1)^kR_{k-2}
$$
with
$$
R_N=Q_N\sum_{k=0}^N\frac{1}{Q_k}
$$
and
$$
Q_k=\left(1-\frac 12\right)\left(1-\frac 14\right)\dots\left(1-\frac{1}
{2^k}\right)\quad\text{for $k\ge 1$}\quad\text{and $Q_0=1$}.
$$
It follows from \cite 2 and \cite 3 that
$$
R_N=N+1-\alpha+R^*(N)
$$
with
$$
\alpha=\sum_{k\ge 1}\frac{1}{2^k-1}=1.606695\dots
$$
and
$$
R^*(z)=\frac{1}{Q_\infty}\sum_{j\ge 1}a_j\frac{z+j}{2^{z+j}-1}.
$$
The quantities in the last equation are
$$
Q_\infty=\lim_{k\to\infty}Q_k=2.88788\dots
$$
and
$$
a_j=(-1)^{j-1}2^{-\binom j2}\big/Q_{j-1}.
$$
We mention for later use that
$$
R^*(-1)=\frac{1}{Q_\infty}
\left[\frac{1}{\L}+\sum_{j\ge 2}a_j\frac{j-1}{2^{j-1}-1}\right]
=2.2346464\dots
$$
(a very fast converging series!).

Therefore
$$
l_N\sim N(\alpha+1)-\Sigma
$$
with
$$
\Sigma=\frac{1}{Q_\infty}\sum_{j\ge 1}a_j
\sum_{k=2}^N\binom Nk(-1)^k\frac{k-2+j}{2^{k-2+j}-1},
$$
and this sum $\Sigma$ will be attacked in the style of Knuth:
Expanding the geometric series we get
$$
\align
\Sigma&=\frac{1}{Q_\infty}\sum_{j\ge 1}a_j
\sum_{m\ge 1}\sum_{k=2}^N\binom Nk(-1)^k(k-2+j)2^{-m(k-2+j)}\\
&\aligned 
=\frac{1}{Q_\infty}\sum_{j\ge 1}a_j\sum_{m\ge 1}
&\left[-N2^{-m(j-1)}\left[(1-2^{-m})^{N-1}-1\right]\right.\\
&\left.+(j-2)2^{-m(j-2)}\left[(1-2^{-m})^{N}-1+\frac{N}{2^m}\right]\right].
\endaligned
\endalign
$$
The last step was by the binomial theorem. Now let
$$
\psi_1(x)=e^{-x}-1\qquad\text{and}\qquad \psi_2(x)=e^{-x}-1+x.
$$
Then the sum $\Sigma$ may be approximated by
$$
\aligned
\Sigma&\sim \frac{1}{Q_\infty}\sum_{j\ge 1}a_j\sum_{m\ge 1}
\left[-\frac{N}{2^{m(j-1)}}\psi_1\left(\frac{N}{2^m}\right)
+\frac{j-2}{2^{m(j-2)}}\psi_2\left(\frac{N}{2^m}\right)
\right]\\
&=:\Sigma_1+\Sigma_2.
\endaligned
$$
This is achieved by the {\it exponential approximation}
$(1-a)^N\approx e^{-aN}$; see e.g. \cite{4; {\rm p.131}}.

Let us start with $\Sigma_1$:
$$
\Sigma_1=-\frac{N}{Q_\infty}\cdot f_1(N)
$$
with
$$
f_1(x)=\sum_{j\ge 1}a_j\sum_{m\ge 1}2^{-m(j-1)}
\psi_1\left(\frac{x}{2^m}\right).
$$
It's Mellin transform  is for $-1<\Re s<0$
$$
\aligned
f_1^*(s)&=\sum_{j\ge 1}a_j\sum_{m\ge 1}2^{-m(j-1)}2^{ms}\Gamma(s)\\
&=\Gamma(s)\cdot\sum_{j\ge 1}a_j\frac{1}{2^{j-1-s}-1}.
\endaligned
$$
The Mellin inversion formula 
$$
f(x)=\frac{1}{2\pi i}\int\limits f^*(s)x^{-s}ds
$$
(where the integration is along a vertical line inside the 
so called {\it fundamental strip}) allows to go back to the
original function. To evaluate it asymptotically,
we have to consider the negative residues of the integrand right of 
the  fundamental strip  (i.e. here at $s=0$).
We don't discuss the other residues which lead to smaller order terms resp.
periodic fluctuations of small amplitude, but this can be done as
easily as the main term.

The term $j=1$ must be treated separately, as it contains a
{\it second order pole}. The residue computation is standard and
gives a contribution
$$
-\frac{N}{Q_\infty}\left(-\log_2N+\frac 12-\frac{\gamma}{\L}\right)
$$
to $\Sigma_1$. For $j\ge 2$ there is only a {\it simple pole},
yielding a contribution
$$
-\frac{N}{Q_\infty}\left[-\sum_{j\ge 2}a_j\frac{1}{2^{j-1}-1}\right].
$$

Now we turn to $\Sigma_2$:
$$
\Sigma_2=\frac{1}{Q_\infty}f_2(N)
$$
with
$$
f_2(x)=\sum_{j\ge 1}a_j(j-2)\sum_{m\ge 1}2^{-m(j-2)}
\psi_2\left(\frac{x}{2^m}\right).
$$
We transform $f_2(x)$: (for $-2<\Re s<-1$)
$$
f_2^*(s)=\Gamma(s)\cdot\sum_{j\ge 1}a_j(j-2)
\frac{1}{2^{j-2-s}-1}.
$$
The pole of interest is this time $s=-1$.

Again, $j=1$ must be treated separately, yielding a contribution
$$
\frac{N}{Q_\infty}\left(-\log_2N+\frac 12+\frac{1}{\L}
-\frac{\gamma}{\L}\right)
$$
to $\Sigma_2$. For $j\ge 2$ the contribution to $\Sigma_2$ is
$$
\frac{N}{Q_\infty}\sum_{j\ge 2}a_j(j-2)\frac{1}{2^{j-1}-1}.
$$
Hence we have 
$$
\aligned
\Sigma_1+\Sigma_2&\sim\frac{N}{Q_\infty}\left(\frac{1}{\L}+
\sum_{j\ge 2}a_j(j-1)\frac{1}{2^{j-1}-1}\right)\\
&=NR^*(-1).
\endaligned
$$
Therefore we obtain the final result
$$
l_N\sim N\big(\alpha+1-R^*(-1)\big)=0.37204\dots\cdot N,
$$
where, again, the {\it ubiquitous}
fluctuating term of order $N$ was not mentioned
for brevity.

\bigskip

\Refs

\ref \no 1\by P.Flajolet, M.R\'egnier and R.Sedgewick
\paper Some Uses of the Mellin Integral Transform in the
Analysis of Algorithms \book Combinatorics on Words
\publ Springer NATO ASI Series F, Vol. 12 \publaddr Berlin \yr 1985 \endref

\ref \no 2\by P.Flajolet and R.Sedgewick\paper Digital Search Trees
Revisited \jour SIAM J. Computing \vol 15 \yr 1986 \pages 748--767
\endref

\ref \no 3\by \by P.Kirschenhofer and H.Prodinger \paper 
Einige Anwendungen der Modulfunktionen in der Informatik
\jour Sitzungsberichte der \"Osterreichischen Akademie
der Wissenschaften \vol 197 \yr 1988 \pages 339--366 \endref

\ref \no 4\by D.E.Knuth\book The Art of Computer Programming, Vol.3
\publ Addison Wesley\publaddr Reading, Mass. \yr 1973 \endref

\endRefs

















\enddocument


