Skip to content

17.2 The accounting method

17.2-1

Suppose we perform a sequence of stack operations on a stack whose size never exceeds $k$. After every $k$ operations, we make a copy of the entire stack for backup purposes. Show that the cost of $n$ stack operations, including copying the stack, is $O(n)$ by assigning suitable amortized costs to the various stack operations.

[We assume that the only way in which COPY is invoked is automatically, after every sequence of $k$ PUSH and POP operations.]

Charge $\$2$ for each $\text{PUSH}$ and $\text{POP}$ operation and $\$0$ for each $\text{COPY}$. When we call $\text{PUSH}$, we use $\$1$ to pay for the operation, and we store the other $\$1$ on the item pushed. When we call $\text{POP}$, we again use $\$1$ to pay for the operation, and we store the other $\$1$ in the stack itself. Because the stack size never exceeds $k$, the actual cost of a $\text{COPY}$ operation is at most $\$k$, which is paid by the $\$k$ found in the items in the stack and the stack itself. Since $k$ $\text{PUSH}$ and $\text{POP}$ operations occur between two consecutive $\text{COPY}$ operations, $k$ of credit stored, either on individual items (from $\text{PUSH}$ operations) or in the stack itself (from $\text{POP}$ operations) by the time a $\text{COPY}$ occurs. Since the amortized cost of each operation is $O(1)$ and the amount of credit never goes negative, the total cost of $n$ operations is $O(n)$.

17.2-2

Redo Exercise 17.1-3 using an accounting method of analysis.

Let $c_i =$ csot of $i$th operation.

$$ c_i = \begin{cases} i & \text{if $i$ is an exact power of $2$}, \\ 1 & \text{otherwise}. \end{cases} $$

Charge each operation $3$ (amotized cost $\hat c_i$).

  • If $i$ is not an exact power of $2$, pay $\$1$, and store $\$2$ as credit.
  • If $i$ is an exact power of $2$, pay $\$i$, using stored credit.

$$ \begin{array}{cccc} \text{Operation} & \text{Cost} & \text{Actual cost} & \text{Credit remaining} \\ \hline 1 & 3 & 1 & 2 \\ 2 & 3 & 2 & 3 \\ 3 & 3 & 1 & 5 \\ 4 & 3 & 4 & 4 \\ 5 & 3 & 1 & 6 \\ 6 & 3 & 1 & 8 \\ 7 & 3 & 1 & 10 \\ 8 & 3 & 8 & 5 \\ 9 & 3 & 1 & 7 \\ 10 & 3 & 1 & 9 \\ \vdots & \vdots & \vdots & \vdots \end{array} $$

Since the amortized cost is $\$3$ per operation, $\sum\limits_{i = 1}^n \hat c_i = 3n$.

We know from Exercise 17.1-3 that $\sum\limits_{i = 1}^n \hat c_i < 3n$.

Then we have

$$\sum_{i = 1}^n \hat c_i \ge \sum_{i = 1}^n c_i \Rightarrow \text{credit} = \text{amortized cose} - \text{actual cost} \ge 0.$$

Since the amortized cost of each operation is $O(1)$, and the amount of credit never goes negative, the total cost of $n$ operations is $O(n)$.

17.2-3

Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it $0$). Counting the time to examine or modify a bit as $\Theta(1)$, show how to implement a counter as an array of bits so that any sequence of $n$ $\text{INCREMENT}$ and $\text{RESET}$ operations takes time $O(n)$ on an initially zero counter. ($\textit{Hint:}$ Keep a pointer to the high-order $1$.)

We introduce a new field $A.max$ to hold the index of the high-order $1$ in $A$. Initially, $A.max$ is set to $-1$, since the low-order bit of $A$ is at index $0$, and there are initially no $1$'s in $A$. The value of $A.max$ is updated as appropriate when the counter is incremented or reset, and we use this value to limit how much of $A$ must be looked at to reset it. By controlling the cost of $\text{RESET}$ in this way, we can limit it to an amount that can be covered by credit from earlier $\text{INCREMENT}$s.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
INCREMENT(A)
    i = 0
    while i < A.length and A[i] == 1
        A[i] = 0
        i = i + 1
    if i < A.length
        A[i] = 1
        // Additions to book's INCREMENT start here.
        if i > A.max
            A.max = i
    else A.max = -1
1
2
3
4
RESET(A)
    for i = 0 to A.max
        A[i] = 0
    A.max = -1

As for the counter in the book, we assume that it costs $\$1$ to flip a bit. In addition, we assume it costs $\$1$ to update $A.max$.

Setting and resetting of bits by $\text{INCREMENT}$ will work exactly as for the original counter in the book: $\$1$ will pay to set one bit to $1$; $\$1$ will be placed on the bit that is set to $1$ as credit; the credit on each $1$ bit will pay to reset the bit during incrementing.

In addition, we'll use $\$1$ to pay to update $max$, and if $max$ increases, we'll place an additional $\$1$ of credit on the new high-order $1$. (If $max$ doesn't increase, we can just waste that $\$1$—it won't be needed.) Since $\text{RESET}$ manipulates bits at positions only up to $A.max$, and since each bit up to there must have become the high-order $1$ at some time before the high-order $1$ got up to $A.max$, every bit seen by $\text{RESET}$ has $\$1$ of credit on it. So the zeroing of bits of $A$ by $\text{RESET}$ can be completely paid for by the credit stored on the bits. We just need $\$1$ to pay for resetting $max$.

Thus charging $\$4$ for each $\text{INCREMENT}$ and $\$1$ for each $\text{RESET}$ is sufficient, so the sequence of $n$ $\text{INCREMENT}$ and $\text{RESET}$ operations takes $O(n)$ time.