AN ASYMPTOTIC COMMENT ON A

PAPER BY ANALYTI AND PRAMANIK

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

In [1] the authors studied (in the context of a hashing problem) the quantity

B(b, m) = \frac{1}{\binom{2^{b}}{m}} ∑_{k=0}^{b} k (\binom{2^{k}}{m}2^{m(b−k)} − \binom{2^{k−1}}{m}2^{m(b−k+1)}) .

They were already successful in approximating B(b, m) by

B(m) = ∑_{k≥0} k (e^{−m^{2}/2^{k+1}} − e^{−m^{2}/2^{k}}) ,

but the further analysis of this quantity is not very precise. The main interest in this short note is to sketch the (by now classical) asymptotic evaluation of this sum. We refer for the necessary details to the brilliant survey [2].

First, it is customary to set x = m^{2}, so that we have

f(x) = ∑_{k≥0} k (e^{−x/2^{k+1}} − e^{−x/2^{k}}) .

The next step is to compute the Mellin transform

f^{∗}(s) = ∫_{0}^{∞} f(x)x^{s−1}dx

= ∫_{0}^{∞} e^{−x}x^{s−1}dx · ∑_{k≥0} k (2^{(k+1)s} − 2^{ks})

= Γ(s) · (2^{s} − 1) ∑_{k≥0} k2^{ks}

= Γ(s) · (2^{s} − 1) \frac{2^{s}}{(2^{s} − 1)^{2}}

= Γ(s) · \frac{2^{s}}{2^{s} − 1}.

Typeset by AMS-TEX

Key words and phrases. Mellin transform.

The original function f(x) is found from the tranformed function f^{∗}(s) by a contour integral:

f(x) = \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞}Γ(s) · \frac{2^{s}}{2^{s} − 1}x^{−s}ds.

This function will be evaluated asymptotically (for x → ∞) by shifting the integral to the right, and collecting the negative residues. The pole at s = 0 is the hardest to handle, since it is a double pole. Since Γ(s) ∼ \frac{1}{s}(1 − γs), \frac{2^{s}}{2^{s}−1} ∼ \frac{1}{s log 2}(1 + \frac{s log 2}{2}), and x^{−s} ∼ 1 − s log x, we find the negative residue at s = 0 to be log_{2} x + \frac{γ}{log 2} − \frac{1}{2}. There are also simple poles at s = 2kπi/ log 2, with negative residue −Γ(\frac{2kπi}{log 2})\frac{1}{log 2}e^{−2kπi·log_{2} x}. This gives a contribution

−\frac{1}{log 2} ∑_{k≠0} Γ( − \frac{2kπi}{log 2})e^{2kπi·log_{2} x},

where we interchanged k and −k for convenience. If we set

δ(x) = \frac{1}{log 2} ∑_{k≠0} Γ( − \frac{2kπi}{log 2})e^{2kπix},

we see that δ(x) is a continuous periodic function of period 1 and small amplitude. Going back to the original sum B(m), we find the result

B(m) = 2 log_{2} m + \frac{γ}{log 2} − \frac{1}{2} − δ(2 log_{2} m) + O(\frac{1}{m^{2}} ).

The authors formula

B(2^{l/2}m) ∼ B(m) + l

is thus an easy consequence of our precise asymptotic formula.

References

1. A.Analyti and S.Pramanik, Performance analysis of a main memory multi-directory hashing technique, Information Processing Letters 45 (1993), 191–197.

2. P.Flajolet and J.Vitter, Average-Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science Vol. A “Algorithms and Complexity”, North-Holland, 1990, pp. 431–524.

TU Vienna Department of Algebra and Discrete Mathematics Wiedner Hauptstrasse 8–10 A-1040 Vienna Austria

E-mail address: proding@email.tuwien.ac.at