 Solution

For an initially zero binary counter, bit $i$ changes precisely on increments whose indices are divisible by $2^i$. Weighting each such change by $2^i$ gives the exact totalFor $n\ge 1$ and $k\ge 1$, put $r=\min \{k,1+\lfloor {\log }_{2}n\rfloor \}$. All summands with $i\ge r$ vanish; each of the other summands is at most $n$. ThereforeThis is sharper than simply charging $n$ for each of all $k$ positions when $n$ is small. To show that the order is best possible, use $\lfloor x\rfloor \ge x/2$ for $x\ge 1$. For every $0\le i<r$,Thus the asymptotic analysis gives a tight bound. If wraparound is excluded, $n<2^k$, and this becomes $\Theta (n(1+{\log }_{2}n))$, often written $\Theta (n\log n)$ for $n\ge 2$. If wraparound is allowed and $n\ge 2^k$, it becomes $\Theta (nk)$. For $n=0$, the cost is zero.

For completeness, the same conclusion cannot be asserted uniformly over arbitrary initial binary counter states. An initial value $2^k-1$ makes the first increment change every bit, costing $2^k-1$. A general upper bound follows by replacing each floor function in the count by a ceiling function:To see the second inequality, split at $r$: for $i<r$, use $\lceil n/2^i\rceil \le n/2^i+1$, and for $i\ge r$, use $\lceil n/2^i\rceil =1$. For $n\ge 1$ the worst initial-state cost is consequently $\Theta (nr+2^k)$. This qualification separates initialization from the usual amortized analysis starting at zero.