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.

- Any overcharge for an operation on an item is stored (in an bank account) reserved for that item.
- Later, a different operation on that item can pay for its cost with the credit for that item.
- The balanced in the (bank) account is not allowed to become negative.
- The sum of the amortized cost for any sequence of operations is an upper bound for the actual total cost of these operations.
- The amortized cost of each operation must be chosen wisely in order to pay for each operation at or before the cost is incurred.

**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:

- 1 unit is used to pay the cost of the PUSH.
- 1 unit is collected in advanced to pay for a potential future POP.

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

C

_{i }=^{ j=1}S_{i}3 - C_{iactual }= 3i - (2^{floor(lg1) + 1 }+i-floor(lgi) - 2)

Ifi= 2, where^{k}k≥ 0, then

C_{i }= 3i- (2^{k+1}+i-k-2)

=k+ 2

Ifi= 2^{k}+j, wherek≥ 0 and 1 ≤j≤ 2, then^{k}

C_{i}= 3i- (2^{k+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 *i*^{th}
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 *C*_{i}
after the *i*^{th} operation is: Since *k* ≥ 1 and
*j* ≥ 1, so credit *C*_{i }always greater
than zero. Hence, the total amortized cost 3*n*, 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 *k**k* 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:

**INCREMENT ( A)**

1.

i= 0

2. whilei< length[A] andA[i] = 1

3. doA[i] = 0

4.i=i+1

5. ifi< length [A]

6. thenA[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.

**INCREMENT ( A)**

1.

i= 1

2. whilei< length [A] andA[i] = 1

3. doA[i] = 0

4.i=i+1

5. ifi< length [A]

6. thenA[i] = 1

7. ifi> 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]

doA[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.