We are going to analyze the running time of an n-bit counter that counts from 0 to 2n 1. For example, when n = 5, the counter has the following values:

Step Value # Bit-Flip

0 00000

1 00001 1

2 00010 2

3 00011 1

4 00100 3

. . . . . .

30 11110 2

31 11111 1

Note that we only need to flip the last bit to go from 0 to 1, but we need to flip the last two bits to go from 1 to 2. It is easy to see that to go from 0 to 2n 1, it takes at most O(n2 n ) bit-flips. Show that, in fact, it takes (2 n ) bit flips. How many times is the last bit flipped? How many times is the second last bit flipped