Cost of increasing a binary counter with a starting value n times

Question

Consider a k-bit binary counter and suppose that in the beginning the value of the i-th most significant bit is $b_i$ for each $i = 0, . . . , k − 1$. Let $b = b_0 + 2b_1 +· · · + 2^{k−1} b_{k−1}$. The cost of each increment is the number of bits flipped. Show that for $n ≥ b$ the cost of $n$ increments from that initial state does not exceed $4n$. Prove that this bound does not necessarily hold if we do not require that $n\ge b$.

I know how to bound the cost of binary counters when they start at 0 using the aggregate method, but I'm not sure how to solve this when we can start at any arbitrary number. My first guess would be to separate out the increments in between $b$ to $2^{k-1}$ and $0$ to $n - (b - 2^{k-1})$ but then I don't see the significance of the $\ge b$ restriction.

Answer 1

Aggregate method $\def\C{\mathcal C}$

The $i$-th bit is flipped every $2^i$ steps.

Imaging the counter was increased from $0$ to $b$ and then from $b$ to $b+n$. The total cost of all $n+b$ increments is: $$(n+b) + \frac{n+b}2 +\frac{n+b}4 + \cdots +\frac{n+b}{2^{\lfloor log_2(n+b)\rfloor}}\le 2(n+b)\le 4n$$

So, the total cost of the last $n$ increments is at most $4n$. $\quad\checkmark$

Potential method.

Assume that you have proved the amortized cost of each increment is at most 2 before. Imagine the counter is increased from $0$ to $b$ and then from $b$ to $b+n$. The total cost of all $b+n$ increments is no more than the total amortized cost of all $b+n$ increments, which is at most $2(b+n)\le 4n$. Of course, the cost of last $n$ increments is no more than the total cost of all $b+n$ increments. $\quad\checkmark$

---

Otherwise, let us start from scratch.

Let $\C$ be the $k$-bit binary counter. The value of $C$ is the binary number represented by $\C$, i.e., $$V(\C)=d_0 + 2d_1 +· · · + 2^{k−1}d_{k−1},$$ where $d_i$ is the value of $i$-th significant bit of $\C$. We may refer to $\C$ at a moment by $V(\C)$ at that moment.

The potential of $\C$ is defined as the number of $1$s in it, i.e.,

$$ \Phi(\C) = d_0 + d_1 +· · · + d_{k−1}$$

---

Let us compute the amortized cost for an increment operation.

Suppose the $j$-th increment reset $t_j$ bits, changing the value of $\C$ to $v_{j-1}$ to $v_{j}$. ($v_0=b$)

The actual cost of the increment, $c_j$ is therefore at most $t_j+1$, since in addition to resetting $t_j$ bits, it sets at most one bit to $1$.

• If $v_j=0$, i.e. $\Phi(v_j)=0$, then the $j$-th increment resets all $k$ bits, and so $\Phi(v_{j-1})=t_j=k$.
• If $v_j>0$, then $\Phi(v_j)=\Phi(v_{j-1})-t_j+1$.

In either case, $\Phi(v_j)\le \Phi(v_{j-1})-t_j+1$, and the potential difference is $$\Phi(v_j)-\Phi(v_{j-1})\le \Phi(v_{j-1})-t_j+1-\Phi(v_{j-1}) = 1 - t_j$$

The amortized cost $$\widehat{c_j}=c_j + \Phi(v_j)-\Phi(v_{j-1})\le (t_j+1)+(1-t_j)=2$$

---

After $n$ increments, the amortized cost $$\sum_{j=1}^n\widehat{c_j}=\sum_{j=1}^nc_j + \Phi(v_n)-\Phi(v_0)\le2n\\ $$ So, $$\begin{aligned} \sum_{j=1}^nc_j &\le 2n -\Phi(v_n)+\Phi(v_0)\le2n -\Phi(v_n)+v_0\\ &=2n-\Phi(v_n)+b=2n-\Phi(v_n)+n= 3n-\Phi(v_n)\le3n\\ \end{aligned}$$

That is, the cost of $n$ increments from the initial state $b$ does not exceed $3n$.

With tighter estimation, we can see that, in fact, the cost is at most $2n + \log_2(b+1)$.