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

$\endgroup$
  • $\begingroup$ Your counter seems to be an ordinary counter that ignores the $i$ least significant bits. $\endgroup$ – Yuval Filmus Mar 22 '14 at 3:46
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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