On Ramanujan's Q(n)-Function
Abstract. This study provides a detailed analysis
of a function which Knuth
discovered to play a central role
in the analysis of hashing
with linear probing.
The function, named after Knuth Q(n),
is related to several of Ramanujan's investigations.
It surfaces in the analysis
of a variety of algorithms and discrete probability problems including
hashing, the birthday paradox, random mapping
statistics, the "rho" method for integer factorization,
union--find algorithms, optimum caching, and the study of memory conflicts.
A process related to the
complex asymptotic methods of singularity analysis and saddle
point integrals permits to precisely quantify the behaviour of the
In this way, tight bounds are derived.
They answer a question of Knuth
(The Art of Computer Programming, Vol. 1, 1968, [Ex. 22.214.171.124.13]),
itself a rephrasing of earlier questions of Ramanujan in 1911-1913.
Here are the addresses of my coauthors:
This paper is available in the Tex, Dvi, and PostScript format.
If you go to the homepage of
you will find, amongst a lot of interesting things, a postscript version of this paper,
which includes the graphics!
(Back to List of Papers)