= Weighted binary counter cost
{title2=$C(n,k)=\sum_{i=0}^{k-1}2^i\lfloor n/2^i\rfloor$}
For an initially zero $k$-bit <binary counter>, suppose changing <bit> $i$ costs $2^i$. It changes exactly $\lfloor n/2^i\rfloor$ times in $n$ increments. Consequently the total is $\Theta(n\min\{k,1+\log_2 n\})$ for $n,k\geq1$. The upper bound counts at most $n$ cost at each active position; the lower bound uses $\lfloor x\rfloor\geq x/2$ for $x\geq1$. This shows why exponential position costs cancel the decreasing carry frequencies that make the ordinary <binary counter> have constant <amortized cost>.
Back to article page
