-1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ Your counter seems to be an ordinary counter that ignores the $i$ least significant bits. $\endgroup$
    – Yuval Filmus
    Mar 22, 2014 at 3:46

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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$
    – Charlie Koch
    Mar 22, 2014 at 6:41
  • $\begingroup$ It's the same as an ordinary counter, so why would there be? $\endgroup$
    – Yuval Filmus
    Mar 22, 2014 at 12:33

Your Answer

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

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