# Amortized analysis of binary counter with increment and resetting operations

I have a question about a specific amortized accounting algorithm and to be specific the variant with Reset operation.

First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$ because for example going from 100 to 101 would set $\max[A]$ to $-1$ which does not make much sense.

Then, "if max[A] increases place 1 dollar as a credit on a new high-order 1." - when the high-order 1 has been set, 2 coins were given for this operation in increment - one for actually setting the bit to 1 and one for for the future, hence eventual reset to 0 would be covered by it. Why do we need to put yet another coin?

• What have you tried? It sounds like you're asking "If I modified the argument as follows, would the proof still go through?" So, have you tried modifying the argument as you propose (to avoid putting another coin), and checking whether all of the subsequent reasoning still goes through or not? That would be a reasonable way to approach this. To help us help you, we ask you to make a serious effort on your own before asking, and to show us in the question what you've tried. – D.W. Jun 5 '15 at 0:58

First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$ does not make much sense.

It does not make sense because it is wrong. This part of code has been wrongly aligned. It should be

5. if i < length [A]
6.   then A[i] = 1
7.       if i > max[A]
8.         then max[A] = i
9.   else max[A] = -1 // the array A overflows; A is effectively reset to 0. So max[A] = -1.


Why do we need to put yet another coin?

As explained in the article, the amortized costs of INC and RESET are $\$$4 and \$$1, respectively. •$\$$4 for INC is composed of • pay \$$1 to set 0 to 1;
• place another $\$$1 on the same bit as credit. The credit on each 1 bit will pay to reset the bit during INC (not by RESET); • pay \$$1 to update max[A] • place an additional$\$$1 of credit on the new high-order 1 (If max[A] does not increase we just waste that one dollar). The credit will pay to reset the bit during RESET. • \$$1 for RESET is

• pay $\$$1 to reset max[A]. Note that the resetting of bits From i = 0 to max[A] is paid for by the credit stored on the bits (each bit reset here has a credit on it due to the last \$$1 for INC). Added: For your specific question on "another$\$$1 on bit 1", note that the first \$$1 credit on each bit 1 put by INC is consumed by the "resetting" part in INC itself (just as in the binary counter without the RESET operation). That is why you need another $\$$1 on each, to pay for the RESET operation (i.e., the code From i = 0 to max[A] A[i] = 0). The charged \$$1 for RESET operation is only for the update of max[A]. • Yes, but my second question was specifically about the last dollar for the INC operation. We already put$\$$1 to set every 0 to 1 (first dollar), but then for some reason we put another \$$ 1 for the high order 1, even though there is already a dollar in there from the initial setting it from 0 to 1. What am I missing? – adaPlease Jun 4 '15 at 18:30
• @adaPlease well. I think we are following different code for Reset operation. In the web page, it is For i = 0 to max[A] do A[i] = 0. In your example, it seems that you are following For i = 0 to max[A] do if(A[i] != 0) A[i] = 0. Do you? If you prefer to your code, please feel free to add an explanation on this situation at the end of my answer. – hengxin Jun 6 '15 at 2:12