(12 pts.) Running times of counting. Consider an n-bit counter that counts from 0 to 2n1. At each step, its value is incremented. For example, when n=5, the counter has the following values: The "Bit-Flips" column shows how many bits need to be flipped at that step. Note that to go from a count of 0 to 1 , we only need to flip the last bit. But when we increase the count from 1 to 2 , we need to flip the last two bits. (a) (4pt) Argue why you need O(n2n) bit-flips to count from 0 to 2n1. (b) (4pt) How many times is the ith bit flipped when we count from 0 to 2n1 ? Assume that the leftmost bit is i=0 and the rightmost bit is i=n1. (Hint: If you're not sure, compute it by hand for the example above. Can you deduce a pattern?) (c) (4pt) Show that, in fact, it takes (2n) bit flips to go from 0 to 2n1. (Hint: Use the answer from part (b))