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

# Bit-Flips 1 Step 0 1 2 3 4 Value 00000 00001 00010 00011 00100 2 1 3 : 30 31 11110 11111 2 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 2" 1, it takes at most O(n2") bit-flips. Show that, in fact, it takes (2") bit flips. (Hint: How many times is the last bit flipped? How many times is the second last bit flipped?)