Problem $3($Binary Counter$)$

a$)$ We perform a sequence of n increment operations on a counter. Assuming that the running

time of each increment operation is proportional to the number of flipped bits in the binary

representation of the numbers, what is the total running time of this sequence?

Example: incrementing from $7$ to $8$ is $0111-->1000,$ resulting in $4$ flipped bits, so the time is

proportional to $4.$

b$)$ What can you conclude about the amortized time of the increment operations for this counter?

Problem $4($Recursion$)$

Describe a simple recursive algorithm that finds the average of n numbers. Draw its call tree and

analyze its running time. See the notes for Lecture $9$ on $9/26$ regarding call trees.

Hint: what is the connection between the average and the sum of n numbers?