Accounting Method


In this method, we assign changes to different operations, with some operations charged more or less than they actually cost. In other words, we assign artificial charges to different operations.


Application 1: Stack Operation

Recall the actual costs of stack operations were:

PUSH (s, x)              1
POP (s)                    1
MULTIPOP (s, k)    min(k,s)

The amortized cost assignments are

PUSH                     2
POP                        0
MULTIPOP            0

Observe that the amortized cost of each operation is O(1). We must show that one can pay for any sequence of stack operations by charging the amortized costs.

The two units costs collected for each PUSH is used as follows:

Therefore, for any sequence for n PUSH, POP, and MULTIPOP operations, the amortized cost is an

Ci   =  j=1Si  3 - Ciactual
      = 3i - (2floor(lg1) + 1 + i -floor(lgi) - 2)
If i  = 2k, where k ≥ 0, then
Ci   = 3i - (2k+1 + i - k -2)
      = k + 2
If i  = 2k + j, where k ≥ 0 and 1 ≤  j ≤  2k, then
Ci  = 3i - (2k+1 + i - k - 2)
     = 2j + k + 2

This is an upperbound on the total actual cost. Since the total amortized cost is O(n) so is the total cost.


As an example, consider a sequence of n operations is performed on a data structure. The ith operation costs i if i is an exact power of 2, and 1 otherwise. The accounting method of amortized analysis determine the amortized cost per operation as follows:
Let amortized cost per operation be 3, then the credit Ci after the ith operation is: Since k ≥ 1 and j ≥ 1, so credit Ci always greater than zero. Hence, the total amortized cost 3n, that is O(n) is an upper bound on the total actual cost. Therefore, the amortized cost of each operation is O(n)/n = O(1).

Another example, consider a sequence of stack operations on a stack whose size never exceeds k. After every k operations, a copy of the entire stack is made. We must 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.
There are, ofcourse, many ways to assign amortized cost to stack operations. One way is:

PUSH                        4,
POP                           0,
MULTIPOP               0,
STACK-COPY         0.

Every time we PUSH, we pay a dollar (unit) to perform the actual operation and store 1 dollar (put in the bank). That leaves us with 2 dollars, which is placed on x (say) element. When we POP x element off the stack, one of two dollar is used to pay POP operation and the other one (dollar) is again put into a bank account. The money in the bank is used to pay for the STACK-COPY operation. Since after kk dollars in the bank and the stack size is never exceeds k, there is enough dollars (units) in the bank (storage) to pay for the STACK-COPY operations. The cost of n stack operations, including copy the stack is therefore O(n). operations, there are atleast



Application 2: Binary Counter

We observed in the method, the running time of INCREMENT operation on binary counter is proportion to the number of bits flipped. We shall use this running time as our cost here.

For amortized analysis, charge an amortized cost of 2 dollars to set a bit to 1.
When a bit is set, use 1 dollar out of 2 dollars already charged to pay the actual setting of the bit, and place the other dollar on the bit as credit so that when we reset a bit to zero, we need not charge anything.

The amortized cost of psuedocode  INCREMENT can now be evaluated:


1. i = 0
2. while i < length[A] and A[i] = 1
3.         do A[i] = 0
4.             i = i +1
5. if i < length [A]
6.             then A[i] = 1

Within the while loop, the cost of resetting the bits is paid for by the dollars on the bits that are reset.At most one bit is set, in line 6 above, and therefore the amortized cost of an INCREMENT operation is at most 2 dollars (units). Thus, for n INCREMENT operation, the total amortized cost is O(n), which bounds the total actual cost.

Consider a Variant

Let us implement a binary counter as a bit vector so that any sequence of n INCREMENT and RESET operations takes O(n) time on an initially zero counter,. The goal here is not only to increment a counter but also to read it to zero, that is, make all bits in the binary counter to zero. The new field , max[A], holds the index of the high-order 1 in A. Initially, set max[A] to -1. Now, update max[A] appropriately when the counter is incremented (or reset). By contrast the cost of RESET, we can limit it to an amount that can be covered from earlier INCREMENT'S.


1. i = 1
2. while i < length [A] and A[i] = 1
3.     do A[i] = 0
4.         i = i +1
5. if i < length [A]
6.     then A[i] = 1
7.     if i > max[A]
8.         then max[A] = i
9.         else max[A] = -1

Note that lines 7, 8 and 9 are added in the CLR algorithm of binary counter.


For i = 0 to max[A]
        do A[i] = 0
max[A] = -1

For the counter in the CLR we assume that it cost 1 dollar to flip a bit. In addition to that we assume that we need 1 dollar to update max[A]. Setting and Resetting of bits work exactly as the binary counter in CLR: Pay 1 dollar to set bit to 1 and placed another 1 dollar on the same bit as credit. So, that the credit on each bit will pay to reset the bit during incrementing.
In addition, use 1 dollar to update max[A] and if max[A] increases place 1 dollar as a credit on a new high-order 1. (If max[A] does not increase we just waste that one dollar). Since RESET manipulates bits at some time before the high-order 1 got up to max[A], every bit seen by RESET has one dollar credit on it. So, the zeroing of bits by RESET can be completely paid for by the credit stored on the bits. We just need one dollar to pay for resetting max[A].
Thus, charging 4 dollars for each INCREMENT and 1 dollar for each RESET is sufficient, so the sequence of n INCREMENT and RESET operations take O(n) amortized time.