Amortised Analysis On K-Bit Counter

The $k$-bit binary counter is a boolean array A[0...k-1] that stores a number in binary, with A[0] as the least significant bit.

• Initially all bits are 0 (i.e. the counter is 0).
• Each index b represents the bit for $2^b$

The structure supports one operation: increment(), which adds $1\mathrm{mod}{2}^k$.

Increment Operation

b = 0
while b < k and A[b] == 1:
    A[b] = 0  # unset bit
    b = b + 1
if b < k:
    A[b] = 1  # set bit

This operation flips some number of consecutive 1s to 0, and then sets the first found 0 to 1. This sequence mimics addition by carrying the 1 to the next iteration (bit).

Example Of A 5-Bit Binary Counter

If $k=5$, then the binary counter represents only $5$ bits.

• To represent the number $13$ (binary 01101), the boolean array stores [1, 0, 1, 1, 0]
• Note how $A[0]=1$ is the least significant (rightmost) digit.

If we run increment() on this, then:

• We traverse through the array, flipping consecutive $1$‘s to $0$‘s;
  • b = 0 -> A[0] = 1 -> [0, 0, 1, 1, 0 ] -> b ++
• We stop if we either reach the end, or we encounter our first 0:
  • b = 1 -> A[1] = 0 -> ...
• If we encounter our first 0 instead of reaching the end, flip it to 1:
  • ... -> 1 < 5 -> [0, 1, 1, 1, 0]

The result is the binary 01110 of $14$

Worst-Case Analysis Of increment()

The run length is the number of iterations of the while loop in increment(), i.e., the number of consecutive 1s before the first 0.

The true cost of increment() is thus proportional to the run length.

• The worst-case run length is $k$, so the worst-case time per operation is $O(k)$.
• Over $n$ increments, this gives a pessimistic bound of $O(n\times k)$.

While some increments flip many bits (are costly), amortised analysis shows that the average cost per increment is low.

The run length is not necessarily equal to the true cost, as it doesn't account for setting the first found 0 to 1

Total Cost Example

• When the counter is $0$:
  • No iterations (run_length = 0)
  • No units of effort
  • total_cost = 0
• When the counter is $1$:
  • One trailing 1 is flipped, i.e. the increment operation iterates once (run_length = 1)
  • There is $1$ unit of effort
  • total_cost = ) + 1 = 1
• When the counter is $2$:
  • One trailing 1 is flipped (run_length = 1), and the first encountered 0 is flipped.
  • There are $2$ unit of effort
  • total_cost = 1 + 2 = 3
• When the counter is $3$:
  • One trailing 1 is flipped (run_length = 1)
  • There is $1$ unit of effort
  • total_cost = 3 + 1 = 4
• When the counter is $4$:
  • Two trailing 1 are flipped (run_length = 2), and the first encountered 0 is flipped.
  • There is $2$ unit of effort
  • total_cost = 4 + 3 = 7
• And so on…

Aggregate Method On K-Bit Binary Counter

To apply this method, we analyse how often each bit flips over n increments. The key idea is to group operations by their run length, i.e., the number of consecutive 1s before the first 0.

• run_length = 0
  • These are the cases where A[0] = 0, requiring just setting A[0] = 1 ($1$ unit of effort)
  • This happens for even values, which are half the numbers.
  • Therefore, there are $\approx \frac{n}{2}$ counter values with A[0] = 0 (approximate as it depends on where the counter stops)
• run_length = 1
  • Considering the remaining $\frac{n}{2}$ values (odd numbers), all of them have a 1 in their LSD.
  • But of those values, half are of the form of the form ...11, and the other half is ...01
  • run_length = 1 are counter values with A[0] = 1 and A[1] = 0 requiring flipping A[0] to 0 in the iterations, and setting A[1] to 1 at the end (2 units of effort)
  • Therefore, there are $\approx \frac{n}{4}$ counter values

Extending this logic (up to $k$), results in:

Run Length	$0$	$1$	$2$	$3$	$4$	$5$	…
Values	$\frac{n}{2}$	$\frac{n}{4}$	$\frac{n}{8}$	$\frac{n}{16}$	$\frac{n}{32}$	$\frac{n}{64}$	…

To compute the total cost, multiply each group count by its respective effort.

Run Length	$0$	$1$	$2$	$3$	$4$	$5$	…
Values	$\frac{n}{2}$	$\frac{n}{4}$	$\frac{n}{8}$	$\frac{n}{16}$	$\frac{n}{32}$	$\frac{n}{64}$	…
Units Of Effort	$1$ unit	$2$ units	$3$ units	$4$ units	$5$ units	$6$ units	…
Respective Effort	$\frac{n}{2}$	$\frac{2n}{4}$	$\frac{3n}{8}$	$\frac{4n}{16}$	$\frac{5n}{32}$	$\frac{6n}{64}$	…

For example, values with run_length 1 require $2$ units of effort each, so total effort for those values is $2\times \frac{n}{4}$

Therefore, the sum of all efforts is

$$\begin{array}{rl}S(n)& =1\cdot \frac{n}{2}+2\cdot \frac{n}{4}+3\cdot \frac{n}{8}+4\cdot \frac{n}{16}+\cdots \\ & =n\cdot \left(\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\frac{4}{16}+\cdots \right)\end{array}$$

This infinite sum converges to $2$:

${\sum }_{i=1}^{\infty }\frac{i}{2^i}=2\to S(n)=2n$

However, the counts $\frac{n}{2},\frac{n}{4},\dots$ are approximate (rounded down), the actual sequence of increments may end before reaching very large run lengths, and the summation ignores any partial increments or leftover bits.

Therefore, this sum provides an upper bound on the total cost:

$T(n)\le 2n$

Hence, the total time over $n$ increments is $O(n)$, and the amortized cost per increment is:

$\frac{T(n)}{n}\le 2=O(1)$

Accounting Method On K-Bit Binary Counter

To apply this method to the increment operation, we break it down into two atomic tasks:

1. The task of flipping a bit from 1 to 0
   • This step occurs inside the while loop and may repeat multiple times per operation.
   • This only happens to bits that were previously set (= 1).
   • Each iteration (i.e. each flip) takes $O(1)$ time.
2. The task of setting a bit from 0 to 1
   • This happens once per increment, after exiting the loop.
   • It also takes $O(1)$ time.
   • It runs at most once, as if all bits are already 1 (i.e. the counter is at $2^k-1$), the loop clears all bits and no 1 is set.

The key is to assign enough coins per increment so that each operation can:

• Pay for its own flipping and setting costs.
• Save extra coins as credit when setting bits to 1, which can later be used to pay for flipping those bits back to 0 in future operations.

Assume that $1$ coin pays for $O(1)$ effort during any part of the increment operation.

Then $\lambda >0$ coin can be allocated each time a bit is set to 1 (just before A[b] = 1 executes).

The coins are then used as follows:

• $1$ coin is then used for the actual bit-setting
• The remaining $\lambda -1$ coins are stored as credit on that bit for future use.

Later, when the bit is flipped from 1 to 0 (in the loop) during a future increment, this credit is then used to pay:

• Each iteration of the loop flips a bit to 0, costing $1$ coin per iteration
• Since each set bit has $\lambda -1$ coins stored on it, we can afford to flip it up to $\lambda -1$ coins

Thus, as long as there’s $\lambda =2$ coins, there’s always enough credit to cover all future un-sets. This ensures:

• No operation goes into debt
• The total amortised cost is bounded by $\lambda$ coins per increment, which is $O(1)$.

Potential Method On K-Bit Binary Counter

We define a potential function $\Phi (D_i)$ as the number of bits set to 1 in the counter after the $i$-th increment operation.

• $\Phi (D_i)$ represents the “stored work”, each 1 will eventually need to be flipped back to 0, costing one unit each.
• Initially, the counter is all zeroes, so $\Phi (D_0)=0$.
• In general, $\Phi (D_i)\ge 0$ for all $i$, and the maximum potential is $k$ when all bits are set.

Let’s analyse the amortised cost of one increment() operation:

• When an increment() is performed, several bits may flip from 1 to 0, and exactly one bit flips from 0 to 1.
• Suppose the number of 1 -> 0 transitions is $l_i$ (i.e., the number of iterations of the while loop).
• Then, the total number of bit operations is $l_i+1$.

The change in potential is thus:

• If $\Phi (D_{i-1})<k$, then $\Phi (D_i)=\Phi (D_{i-1})-l_i+1$
• If $\Phi (D_{i-1})=k$, then $\Phi (D_i)=\Phi (D_{i-1})-l_i$

From the amortised cost:

$a_i={\tau }_i+\Phi (D_i)-\Phi (D_{i-1})$

Substituting the two expressions into it results in:

$$a_i=\{\begin{array}{ll}(l_i+1)+(\Phi (D_{i-1})-l_i+1-\Phi (D_{i-1}))=2,& \text{if }\Phi (D_{i-1})<k\\ & \\ (l_i+1)+(\Phi (D_{i-1})-l_i-\Phi (D_{i-1}))=1,& \text{if }\Phi (D_{i-1})=k\end{array}$$

In both cases, $a_i\le 2$, so the amortised cost per operation is $O(1)$. Over $n$ increments, the total amortised time is $O(n)$.