File BinaryCounter.h

↰ Parent directory (ADS/algorithm)

The binary counter of k bits of the amortized analysis: A[ 0 ] is the least significant bit, and add() increments the counter modulo :math:` 2^k `.

Definition (`ADS/algorithm/BinaryCounter.h`)

Program Listing for File BinaryCounter.h

Detailed Description

One increment changes up to k bits, but n increments change at most :math:`[: sum_{i=0}^{k-1} leftlfloor frac{n}{2^i} rightrfloor < n sum_{i=0}^{infty} frac{1}{2^i} = 2 n

` bits, since A[ i ] changes every :math:` 2^i ` increments: the amortized cost of an increment is O( 1 ). The same bound comes from the potential :math:` Phi ` = the number of bits equal to 1: an increment that clears d bits and sets one costs d + 1 and changes :math:` Phi ` by 1 - d, hence its amortized cost is 2.

The contracts [see File Contract.h]: the counter holds only bits, an audit, and add() changes at most k of them. The functions are defined in BinaryCounter.tpp.