PERIODIC OSCILLATIONS IN THE ANALYSIS OF ALGORITHMS
HELMUT PRODINGER
Abstract. A large number of results in analysis of algorithms contain fluctuations.
A typical result might read "The expected number of ...for large Т behaves like
log2 Т+constant+Ж(log2 Т), where Ж(Ь) is a periodic function of period one and mean
zero." Examples include various trie parameters, approximate counting, probabilistic
counting, radix exchange sort, leader election, skip lists, adaptive sampling. Often,
there are huge oscillations to be noted, especially if one wants to compute variances.
In order to see this, one needs identities for the Fourier coefficients of the periodic
functions involved. There are several methods to derive such identities, which belong
to the realm of modular functions. The most flexible one seems to be the calculus
of residues. In some situations, Mellin transforms help. Often, known identities can
be employed. This survey shows the various techniques by elaborating on the most
important examples from the literature.
1. БТШЦУ Щ Ш УТ
A surprisingly large number of results in analysis of algorithms contain uctua-
tions. A typical result might read "The expected number of . . . for large Т behaves like
log2 Т + constant + Ж(log2 Т), where Ж(Ь) is a periodic function of period one and mean
zero." Examples include various trie parameters, approximate counting, probabilis-
tic counting, radix exchange sort, leader election, skip lists, adaptive sampling; see the
classic books by Flajolet, Knuth, Mahmoud, Sedgewick, Szpankowki [20, 14, 15, 16, 21]
for background.
–1.5e–06
–1e–06
–5e–07
0
5e–07
1e–06
1.5e–06
–2
–1
1
2
x
5e–13
1e–12
1.5e–12
2e–12
2.5e–12
–2
–1
1
2
x
ЩЦ Ѕє Ж0(Ь) and Ж
2
0(Ь)
As one can see from the picture, Ж0(Ь) has mean zero (the zeroth Fourier coefficient
is not there). On the other hand, Ж
2
0(Ь) is still periodic with period 1, but its mean is
not zero. Why should we worry about a quantity apparently as small as
10
12?
Key words and phrases. Periodic oscillations, residues, Mellin transform, Dedekind's eta functions,
modular functions, analysis of algorithms, tries, approximate counting, geometric random variables.
1
2
H. PRODINGER
–0.0002
–0.0001
0
0.0001
0.0002
–2
–1
1
2
x
ЩЦ ѕє The functions 1
log 2
И
=0
( ¾
РУ ¾
)
2
Ь grow in amplitude
with
The reason is the variance of such parameters, as it naturally contains the term
"-expectation2," and as such also -Ж
2(Ь). That might not be a sufficient motivation
for a casual reader if it were not the case that often substantial cancellations occur. In
order to identify them, one has to know more about Ж
2(Ь). If one ignores these terms,
one gets wrong results, and the results are not wrong by
10
12, but by an order of
growth! Path length in tries, Patricia tries, and digital search trees [7, 13, 9] are such
cases: the variance is in reality of order Т only, but ignoring the fluctuations would
lead to a (wrong)
Т
2 result.
Questions like that occurred in several writings of this author (together with various
coauthors), as can be seen from the references. The techniques are extremely interest-
ing, as one has to dig deep into classical analysis. So far, it seems that the calculus
of residues is the most versatile approach in this context. Another approach is to use
(modular) identities due to Dedekind, Ramanujan, Jacobi and others (which can often
be proved by Mellin transform techniques); however, often they do not quite fit. The
residue calculus approach directly addresses the formula that is ultimately needed.
In this survey paper, we discuss all these methods by looking at various examples.
Oscillating functions are usually given as Fourier series
=
И
=0
2
Ь, thus
representing a periodic function of period 1, and since the term 0 is missing, oscillating
around zero. We often refer to the coefficient
by writing [ ] .
Here are some examples from the literature.
Approximate counting. [5, 10, 18, 19]
After Т successive increments the average content Т of the counter satisfies:
Т ~ log2 Т +
Д
-« +
1
2
-Ж0(log2 Т)
with
« =
1
1
2 -1
and Ж0(Ь) =
1
Д
=0
Γ(- ) 2
Ь
with Д = log 2 and
= 2
Д . The identity that one needs is
[Ж
2
0]0 =
1
Д
2
=0
Γ( )Γ(- ) =
2
6Д
2 - 11
12
- 2
Д
1
(-1)
1
(2 -1)
(1.1)
PERIODIC OSCILLATIONS IN THE ANALYSIS OF ALGORITHMS
3
Maximum of a sample of Т geometric random variables. [22, 11]
Assume that
is a geometric random variable such that И{ = } = 2
(for
simplicity, we only discuss this case, not the slightly more general И{ = } = (1 -
Х)Х 1). We consider Т independent trials and look for the maximum of them. This
is a natural parameter which is also useful in the analysis of various algorithms (e.g.,
skiplists [12]).
The expected value is given by
Т ~ log2 Т +
Д
+
1
2
-Ж0 (log2 Т)
with the same periodic function as before.
Tries. [10, 7]
The expected number of internal nodes in a trie built from Т random data
РТ ~ Т
Д
+ Т(log2 Т)
with
(Ь) =
1
Д
=0
Γ(1 - ) 2
Ь
The formula that one needs is
[ 2]0 = 3 - 1
Д
- 1
Д2
+
2
Д
2
(-1)
( + 1)( -1)(2 -1)
Partial match queries in tries. [8]
The average cost (defined in the paper [8]), for random tries constructed from Т
random data, is
РТ ~/Т
/ 1 +
/
2
2Д
+
log2
/
Т
¡
where the fluctuating function (Ь) =
И
=0
2
Ь has the Fourier coefficients
=
1
2Д
1 +
/
2(-1) Γ
-1 -
2
-1 +
2
(1.2)
The formula one needs is
[ 2]0 =
3
4Д
-
4Д
2
3+2
/
2
¡
+
3 -2
/
2
Д
(Д) +
2
/
2
Д
Д
2
with
(Ь) =
1
Ь
1 + 2 Ь
4
H. PRODINGER
2. ИЦУУ × Э Ц × Щ Р ЩРЩЧ
The following approach to evaluate [Ж
2]0 seems to be the easiest and most flexible.
We start with the following example:
Ж0(Ь) =
1
Д
=0
Γ(- ) 2
Ь
Find a function (Ю) so that [Ж
2
0]0 is (apart from a few extra terms) the sum of the
residues along the imaginary axis. Here, take
(Ю) =
Д
ДЮ -1
Γ(-Ю)Γ(Ю)
If we set
Б1 =
1
2
½
¾
+ ½
½
¾ ½
(Ю) Ю
then by shifting and collecting residues,
Б1 =
1
2
½
¾
+ ½
½
¾ ½
(Ю) Ю +
=0
Γ(- )Γ( ) - 2
6
- Д
2
12
Now one writes
1
Ю -1
= -1 - 1
Ю -1
and gets, by a simple change of variable Ю := -Ю,
Б1 = - 1
2
½
¾
+ ½
½
¾ ½
Γ(-Ю)Γ(Ю) Ю -Б1 +
=0
Γ(- )Γ( ) - 2
6
- Д
2
12
The integral
Б2 = - 1
2
½
¾
+ ½
½
¾ ½
Γ(-Ю)Γ(Ю) Ю
can be computed by collecting the negative residues right to the line пЮ = -1
2
, viz.
Б2 = - 1
2
½
¾
+ ½
½
¾ ½
Γ(-Ю)Γ(Ю) Ю =
Р 1
(-1)Р
Р!
(Р -1)! = -Д
Altogether we have
2Б1 = -Д +
=0
Γ(- )Γ( ) - 2
6
- Д
2
12
On the other hand, integral Б1 is also the sum of the negative residues right of the line
пЮ = 1
2
, i. e.,
Б1 = -Д
Р 1
(-1)Р
Р!(2Р -1)
(Р -1)! = -Д
Р 1
(-1)Р
Р(2Р -1)
Combining these results, we get
-2Д
Р 1
(-1)Р
Р(2Р -1)
= -Д +
=0
Γ(- )Γ( ) - 2
6
- Д
2
12
PERIODIC OSCILLATIONS IN THE ANALYSIS OF ALGORITHMS
5
This is the identity we wanted.
With not much more effort one can also compute the coefficients [Ж
2
0] , for = 0.
For this, one works with the function
(Ю) =
Д
ДЮ -1
Γ(-Ю - )Γ(Ю)
One obtains
[Ж
2
0] =
1
Д
2
=0 =
Γ(- )Γ(- + )
=
2
Д
Р 1
(-1)РΓ(- + Р)
Р!(2Р -1)
+
2
Д
2
Γ(- )
(- ) +
¡
We omit the details.
Guy Louchard, who is interested in higher moments, asked to compute the coeffi-
cients [Ж
3
0] . Here is the instance = 0, the general case is very involved and not too
attractive:
[Ж
3
0]0 = -1 - 2 (3)
Д3
- 1
Д
Р 1
(-1)Р
Р(2Р -1)
+
6
Д2
Р 1
(-1)РАР 1
Р(2Р -1)
+
2 log 3
Д
+
2
Д
Р 1
(-1)Р+
(Р + )(2Р -1)
1
2 -1
+
1
2 +Р -1
Р +
(In this formula, the harmonic numbers АТ :=
И
1
Т
1 appear.)
This has been tested numerically as well and gives 9 42817763095796606421903 χ
10
25.
Let us straight ahead do another example, which also occurs often:
(Ь) =
1
Д
=0
Γ(-1 - ) 2
Ь
Here, we take
(Ю) = - Д
ДЮ -1
Ю
2Γ(-1 -Ю)Γ(-1 + Ю)
Then
Б1 =
1
2
½
¾
+ ½
½
¾ ½
(Ю) Ю +
=0
(- )Γ(-1 - )Γ(-1 + )+1
and
2Б1 = ДБ2 +
=0
(- )Γ(-1 - )Γ(-1 + )+1
with
Б2 =
1
2
½
¾
+ ½
½
¾ ½
Ю
2Γ(-1 -Ю)Γ(-1 + Ю) Ю =
Р 2
Р
2 (-1)Р+1
(Р + 1)!
(Р -2)! +
Д
4
=
Р 2
(-1)Р+1
Р
(Р + 1)(Р -1)
= -Д +
1
4
+
1
4
= -Д +
1
2
6
H. PRODINGER
Therefore
2Б1 = -Д
2 +
Д
2
+
=0
(- )Γ(-1 - )Γ(-1 + )+1
But Б1 is also
Б1 = -Д
4
+ Д
2 + Д
Р 2
Р
2
2Р -1
(-1)Р+1
(Р + 1)!
(Р -2)! = -Д
4
+ Д
2 + Д
Р 2
(-1)Р+1
Р
(2Р -1)(Р + 1)(Р -1)
Putting things together, we find
2Б1 = -Д
2 +
Д
2
+
=0
(- )Γ(-1 - )Γ(-1 + )
= -Д
2
+ 2Д
2 + 2Д
Р 2
(-1)Р+1
Р
(2Р -1)(Р + 1)(Р -1)
+ 1
or
=0
(- )Γ(-1 - )Γ(-1 + ) = -1 -Д + 3Д
2 + 2Д
Р 2
(-1)Р+1
Р
(2Р -1)(Р + 1)(Р -1)
which is the identity in question, as it expresses the quantity Д
2[ 2]0 in two different
ways.
Here is a third example, dealing with the function
1
Д
0
Γ( - ) 2
Ь
for >1 and the computation of the constant term of its square. The technique should
be familiar by now. Consider the function
Д
Γ( + Ю)Γ( -Ю)
ДЮ -1
Therefore we have
=0
Γ( + )Γ( - ) =
Д
2
½
¾
+ ½
½
¾ ½
Γ( + Ю)Γ( -Ю)
ДЮ -1
Ю
- Д
2
½
¾
+ ½
½
¾ ½
Γ( + Ю)Γ( -Ю)
ДЮ -1
Ю -Γ( )2
(Γ( )2 is the residue at Ю = 0.)
Now we use again the decomposition
1
ДЮ -1
= -1 - 1
ДЮ -1
PERIODIC OSCILLATIONS IN THE ANALYSIS OF ALGORITHMS
7
for the second integral and get
- Д
2
½
¾
+ ½
½
¾ ½
Γ( + Ю)Γ( -Ю)
ДЮ -1
Ю
=
Д
2
½
¾
+ ½
½
¾ ½
Γ( + Ю)Γ( -Ю) Ю +
Д
2
½
¾
+ ½
½
¾ ½
Γ( + Ю)Γ( -Ю)
ДЮ -1
Ю
=
Д
2
½
½
Γ( + Ю)Γ( -Ю) Ю +
Д
2
½
¾
+ ½
½
¾ ½
Γ( -Ю)Γ( + Ю)
ДЮ -1
Ю
Therefore
=0
¬¬Γ( + )¬¬2
=
2Д
2
½
¾
+ ½
½
¾ ½
Γ( + Ю)Γ( -Ю)
ДЮ -1
Ю +
Д
2
½
½
Γ( + Ю)Γ( -Ю) Ю -Γ( )2
= Б1 + Б2 -Γ( )2
Integral Б1 is evaluated by shifting the contour to the right and collecting the negative
residues, which gives
Б1 = -2Д
С
Γ( + С)
ДС -1
(-1)
С+1
(С - )!
and with С = +
= 2Д
0
( + 2 -1)!(-1)
!
1
2 + -1
= 2Д(2 -1)!
0
-2
1
2 + -1
Integral Б2 is of interest for itself and appears already in early references to the Mellin
transform technique as by Nielsen [17, p. 224]. (It could, however, by computed as in
the previous examples.)
We start with the function
(Ь) =
Ь
(1 + Ь)2
and perform its Mellin transform (see, e.g., [6] for definitions)
£
(×) =
½
0
(Ь)Ь
× 1
Ь = ( + × -×) =
Γ( + ×)Γ( -×)
Γ(2 )
with the Beta function (Ю Ы) (compare [1]). The fundamental strip is (- ). There-
fore the inversion formula for the Mellin transform gives
(Ь) =
1
2
½
½
Γ( + ×)Γ( -×)
Γ(2 )
Ь
×
×
8
H. PRODINGER
Now we may evaluate at Ь = 1 and get the formula
1
2
½
½
Γ( + ×)Γ( -×) × = Γ(2 )2
2
This produces the formula
=0
Γ( + )Γ( - )
= 2Д(2 -1)!
0
-2
1
2 + -1
+ Д(2 -1)!2
2 -( -1)!2
Remark. The computation of the integral Б2 (as in the examples above) sometimes
leads to series like
Р 1
(-1)Р
Р
There is nothing wrong here. The correct interpretation is as an Abel limit
lim
Ш 1
Р 1
(-1)Р
РШ
Р = lim
Ш 1
-Ш
(1 + Ш)2
= -1
4
3. НЧ Т Ш Е РР Т ШЦ ТЧ УЦС
Let us start with our running example (1.1) and show how this can be proved using
the Mellin transform. This technique is very prominent in the analysis of algorithms,
and we refer to [6] for a nice survey.
We might for instance start with the series
1
(-1)
1
(2 -1)
and interpret it as (log 2) with
(Ь) :=
1
(-1)
1
( Ь -1)
=
1
(-1)
1 Ь
Now one computes the Mellin transform
£
(×):
£
(×) =
1
(-1)
1 Ь =
1
(-1)
1 × ×Γ(×) = (1 -2
×) (× + 1) (×)Γ(×)
Using the inversion formula for the Mellin transform, one gets
(Ь) =
1
2
¿
¾
+ ½
¿
¾ ½
(1 -2
×) (× + 1) (×)Γ(×)Ь
×
×
=
2
12Ь
- Д
2
+
Ь
24
+
1
2
¿
¾
+ ½
¿
¾ ½
(1 -2
×) (× + 1) (×)Γ(×)Ь
×
×
=
2
12Ь
- Д
2
+
Ь
24
+
1
2
¿
¾
+ ½
¿
¾ ½
(2× -1) (× + 1) (×)
1
2
/ Γ
×
2
Γ
× + 1
2
Ь
×
×
PERIODIC OSCILLATIONS IN THE ANALYSIS OF ALGORITHMS
9
This form was obtained by taking 3 residues out and invoking the duplication formula
of the Γ-function. (Observe that the exponential smallness of the Γ-function along
vertical lines justifies the shifting of the line integral.) We now use the functional
equation for (×), namely
Γ
×
2
(×) = × ½
¾ Γ
1 -×
2
(1 -×)
(3.1)
and continue:
(Ь) =
2
12Ь
- Д
2
+
Ь
24
+
1
2
¿
¾
+ ½
¿
¾ ½
(2× -1)
1
2
2× ½
¾ Γ
1 -×
2
(1 -×)Γ
-×
2
(-×)Ь
×
×
=
2
12Ь
- Д
2
+
Ь
24
+
1
2
¿
¾
+ ½
¿
¾ ½
(2
× -1)
1
2
2× ½
¾ Γ
1 + ×
2
(1 + ×)Γ
×
2
(×)Ь
×
×
=
2
12Ь
- Д
2
+
Ь
24
- 1
2
¿
¾
+ ½
¿
¾ ½
(1 -2
×)
2× (1 + ×) (×)Γ(×)Ь
×2
×
×
and so
(Ь) =
2
12Ь
- Д
2
+
Ь
24
- 2 2
Ь
(3.2)
This is the formula we need, since we can also rewrite the left side of (1.1) in terms of
this (Ь) function:
[Ж
2
0]0 =
1
Д
2
=0
Γ( )Γ(- ) =
1
Д
1
1
sinh(2 2
Д)
=
2
Д
1
Ю
( 2 Ю -1)
with Ю = 2 2
Д. But
1
Ю
( 2 Ю -1)
=
1
0
1 (2 +1)Ю =
1
1
1 Ю -2
1
1
1
2
2 Ю
=
1
1
(-1)
1 Ю =
1
(-1)
1
( Ю -1)
= (Ю)
and so
[Ж
2
0]0 =
2
Д
2 2
Д
Let us do a more complicated example in the same style: We want to rewrite [ 2]0,
with the Fourier coefficients given in (1.2). Note that
[ 2]0 = 2
1
=
2
4Д
2
1
3+2
/
2(-1) Γ
1 -
2
Γ
1 +
2
10
H. PRODINGER
Now we use the formula (reflection formula for the Gamma function, cf. [1]) Γ(Ю)Γ(1-
Ю) =
sin Ю and obtain
Γ
1 -
2
Γ
1 +
2
=
sin( 2 +
2
Д)
=
cos(
2
Д)
=
cosh( 2
Д)
= 2
¾ Д
1 + 2 ¾ Д
so that
[ 2]0 =
Д
2
1
3+2
/
2(-1)
¾ Д
1 + 2 ¾ Д
(3.3)
Let us define two new functions
(Ь) =
1
Ь
1 + 2 Ь
and
(Ь) =
1
(-1)
1 Ь
1 + 2 Ь
Then, (3.3) in terms of (Ь) and (Ь) becomes
[ 2]0 =
3
Д2
2
Д
- 2
/
2
Д2
2
Д
(3.4)
We use a series transformation for (Ь) and (Ь). We start with
(Ь) =
0
(-1)
1
(2 +1)Ь =
0
( )
1
Ь -1
where
( ) =
0
for even
1
for ξ1 mod 4
-1 for ξ3 mod 4
Once we know
(Ь) =
4Ь
- 1
4
+
Ь
2
Ь
(3.5)
for Ь 0, as we shall show soon, then (Ь) = (Ь) -2 (2Ь), hence
(Ь) =
1
4
+
Ь
2
Ь
-
Ь
2
2Ь
Applying the above to (3.4) we finally obtain
[ 2]0 =
3
4Д
-
4Д
2
3+2
/
2
¡
+
3 -2
/
2
Д
(Д) +
2
/
2
Д
Д
2
To prove (3.5) we proceed as follows. Let
¬(×) =
0
(-1)
1
(2 + 1)×
We have
(Ь) =
1
Ь
1 + 2 Ь
=
0
(-1)
1
(2 +1)Ь
PERIODIC OSCILLATIONS IN THE ANALYSIS OF ALGORITHMS
11
so that the Mellin transform
£
(×) =
К
½
0
(Ь)Ь× 1
Ь of (Ь) becomes
£
(×) =
Γ(×) (×)¬(×). By the Mellin inversion formula this yields
(Ь) =
1
2
¿
¾
+ ½
¿
¾ ½
Γ(×) (×)¬(×)Ь
×
×
Now we take the two residues × = 1 and × = 0 out from the above integral (observe
that ¬(0) = 1 2 and ¬(1) =
4, cf. [1]) and apply the duplication formula for Γ(×) to
obtain
(Ь) =
4Ь
- 1
4
+
1
2
½
¾
+ ½
½
¾ ½
1/ 2× 1Γ
×
2
Γ
× + 1
2
Ь
× (×)¬(×) ×
We now use the functional equations for (×) and ¬(×), namely
Γ
×
2
(×) = × ½
¾ Γ
1 -×
2
(1 -×)
and
¬(1 -×)Γ 1 - ×
2
= 22× 1 ×+½
¾ Γ
× + 1
2
¬(×)
The first identity is Riemann's functional equation for (×), and the second an imme-
diate consequence of the functional equation for Hurwitz's -function (× ) (cf. [2]),
and the fact that
¬(×)=4
×
×
1
4
¡
-
×
3
4
¡
Substituting 1 -× = Щ, we get
(Ь) =
4Ь
- 1
4
+
1
2
¿
¾
+ ½
¿
¾ ½
1 2ЩΓ(Щ)Ь
Щ 1 (Щ)¬(Щ) Щ
which proves (3.5).
Using the above scheme, several other identities which one needs in the analysis of
algorithms can be proved. We refer to Szpankowski's book [21].
4. ЕУ ЩР Ц ТШ Ш ×
Formul like (3.2) belong to the realm of modular functions. Many of them can
be found in the literature, and are due to Jacobi, Dedekind, Ramanujan and others.
Berndt's book [4] contains a wealth of information about the subject, compare also [3].
Here is a little bit of background: Let А be the upper complex halfplane {Ю G |
Ю 0}. Then the Dedekind function is defined by
( ) =
12
Т 1
1 - 2 Т ¡
GА;
there is a transformation formula:
-1
= (- )1 2 ( )
Ramanujan considered series
(Ю) :=
1
С
2 Ю -1
С an odd integer,
12
H. PRODINGER
and could relate them to ( 2
Ю). The instance С = -1 is equivalent to the functional
equation for Dedekind's eta function.
К Ц Т ×
[1] M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions. Dover, 1973. A reprint
of the tenth National Bureau of Standards edition, 1964.
[2] T. Apostol. Introduction to Analytical Number Theory. Springer, 1976.
[3] T. Apostol. Modular Functions and Dirichlet Series in Number Theory. Springer, 1978.
[4] B. Berndt. Ramanujan's Notebooks. Part II. Springer, 1989.
[5] P. Flajolet. Approximate counting: A detailed analysis. BIT, 25:113-134, 1985.
[6] P. Flajolet, X. Gourdon, and P. Dumas. Mellin transforms and asymptotics: Harmonic sums.
Theoretical Computer Science, 144:3-58, 1995.
[7] P. Kirschenhofer, H. Prodinger, and W. Szpankowski. On the variance of the external path length
in a symmetric digital trie. Discrete Applied Mathematics, 25:129-143, 1989.
[8] P. Kirschenhofer, H. Prodinger, and W. Szpankowski. Multidimensional digital searching and
some new parameters in tries. International Journal of Foundations of Computer Science, 4:69-
84, 1993.
[9] P. Kirschenhofer, H. Prodinger, and W. Szpankowski. Digital search trees again revisited: The
internal path length perspective. SIAM Journal on Computing, 23:598-616, 1994.
[10] P. Kirschenhofer and H. Prodinger. On some applications of formul of Ramanujan in the analysis
of algorithms. Mathematika, 38:14-33, 1991.
[11] P. Kirschenhofer and H. Prodinger. A result in order statistics related to probabilistic counting.
Computing, 51:15-27, 1993.
[12] P. Kirschenhofer and H. Prodinger. The path length of random skip lists. Acta Informatica,
31:775-792, 1994.
[13] P. Kirschenhofer, H. Prodinger, and W. Szpankowski. On the balance property of Patricia tries:
external path length viewpoint. Theoret. Comput. Sci., 68:1-17, 1989.
[14] D. E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms. Addison-
Wesley, 1973. Third edition, 1997.
[15] D. E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-
Wesley, 1973. Second edition, 1998.
[16] H. M. Mahmoud. Evolution of Random Search Trees. John Wiley, New York, 1992.
[17] N. Nielsen. Handbuch der Theorie der Gammafunktion. Teubner, 1906.
[18] H. Prodinger. Hypothetic analyses: Approximate counting in the style of Knuth, path length in
the style of Flajolet. Theoretical Computer Science, 100:243-251, 1992.
[19] H. Prodinger. Approximate counting via Euler transform. Mathematica Slovaka, 44:569-574,
1994.
[20] R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley,
1996.
[21] W. Szpankowski. Average case analysis of algorithms on sequences. Wiley-Interscience, New York,
2001.
[22] W. Szpankowski and V. Rego. Yet another application of a binomial recurrence. Order statistics.
Computing, 43:401-410, 1990.
Helmut Prodinger, The Вohn ГnopFmacher Centre For Applicable Analysis and
Number Theory, School oF Mathematics, Нniversity oF the Пitwatersrand, Private
ag 3, Пits, 2050 Вohannesburg, South AFrica
E-mail address: helmut@maths.wits.ac.za
