Approximate counting with m counters: A detailed analysis
Date
2012
Authors
Prodinger H.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The classical algorithm approximate counting has been recently modified by Cicho and Macyna: instead of one counter, m counters are used, and the assignment of an incoming item to one of the counters is random. The parameter of interest is the sum of the values of all the counters. We analyse expectation and variance, getting explicit and asymptotic formulæ. © 2012 Elsevier B.V. All rights reserved.
Description
Keywords
Approximate counting, Cancellations, q-analysis, Rice's method
Citation
Theoretical Computer Science
439
58
68
439
58
68