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...

  • $\begingroup$ Your counter seems to be an ordinary counter that ignores the $i$ least significant bits. $\endgroup$ Commented Mar 22, 2014 at 3:46

1 Answer 1


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.

  • $\begingroup$ I already realized that, as I said in my question. But is there any difference in the amortize calculation than an ordinary counter? $\endgroup$ Commented Mar 22, 2014 at 6:41
  • $\begingroup$ It's the same as an ordinary counter, so why would there be? $\endgroup$ Commented Mar 22, 2014 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.