On the analysis of probabilistic counting

Abstract. In this note an alternative analysis of a probabilistic counting algorithm due to Flajolet and Martin is presented. The asymptotic evaluation of certain combinatorial sums is performed via residue calculus instead of Flajolet's Mellin transform approach that had to use some unpleasant real analysis.


This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)