Suppose that we have a binary counter with k bits where each

Suppose that we have a binary counter with k bits, where each bit is stored in a array A[0..k 1]. The operation Increment(A) increments the counter by adding 1 to the content of the counter modulo 2k . The cost of this operation is proportial the number of bits that need to be inspected, so it is at most O(k).

a) Prove that if a sequence of n increment operations is applied to a counter that is initially zero, then at most 2n bits are flipped, by counting the number of bit flips. [Hint: Note that A[0] flips every time, A[1] flips every other time, etc.]

b) Use now the accounting method to prove that at most 2n bits are flipped, when a sequence of n increment operations is executed on a counter that is initially zero.

Solution

We know each bit represent 2 values. Therefore for n-bits we will have 2^n values.

Part a.) Let n=2; so, we will have 4 values i.e. 0-3. Now, we have

00 -> 01 -> 10 -> 11 ->00

As we can see LSB is flipping at each state and MSB is flipping after 2 states. So, in total we have 3 + 1 = 4 flips which is 2n.

Now, for n-bit binary counter, LSB flips n-1 times, and bit next to LSB flips n times and so on. Now, total no. of flips are n + n/2 + n/4+ ..+ 1 = 2n (approx.)

Hope it helps, do give your response.