Approximate counting with m counters: A probabilistic analysis

Guy Louchard, Helmut Prodinger

Abstract


Motivated by a recent paper by Cicho\'n and Macyna [1], who introduced $m$ counters (instead of just one) in the approximate counting scheme first analysed by Flajolet [2], we analyse the moments of the sum of the $m$ counters, using techniques that proved to be successful already in several other contexts [11].

Keywords


Approximate counting, Moments, Constant and fluctuating components, Complex analysis, Product ofFourier series

Full Text:

PDF

Refbacks

  • There are currently no refbacks.


ISSN: 2148-838X