# Custom binary counter supports only increment in $2^i$ values amortized analysis

I'm a having trouble analyzing this algorithm. This is a binary counter that supports only increments in $2^i$ values it's implemented in this way: starting from the $i$-th location change all the straight $1$'s to $0$'s and the first $0$ to $1$.

So I analyzed the W.C to be $O(\log n)$ because the worst case is we need to increment by $1$ a $2^i-1$ number. Now for the amortized I thought using the accounting method, charging for each change from $0$ to $1$ $2\$$amortized cost, since each time we increment we flip at most one 0 to 1. and put 1\$$ on each$1$bit to pay from flipping it back to$0$. so at most the amortized cost is$2\ which means amortized $O(n)$. if it's correct than what's the difference from a regular binary counter? I don't think I understand...

• Your counter seems to be an ordinary counter that ignores the $i$ least significant bits. – Yuval Filmus Mar 22 '14 at 3:46

The counter you describe is a completely ordinary counter with an extra "appendage" which consists of the $i$ least significant bits. Those are never accessed by the algorithm, and the rest of the bits operate like an ordinary counter.