counting.tex

\chapter{Counting}

\section{Binary Counters}

Amortized efficiency of binary counters for increment-only operations.

\section{Redundant Binary Counters}

Counters that support increment and decrement in $O(1)$ amortized time

\section{Worst-Case Efficient Counters}

Counters that represent $(2-\epsilon)2^{n-1}$ different values using $n$
bits and can be incremented in $O(\log n)$ worst-case time.

\section{Discussion and References}