Approximate counting with m counters: A detailed analysis
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.