*Accounting Method*is an elegant technique for amortized analysis of the data structures. Most of us should have encountered

*Dynamic data structures*(which need to expand and contract to maintain some invariant) at some point of time. A stack implementation is one example of a dynamic data structure. As we perform

*pop*operation on the stack eventually it become full (

*over-flow*), at this stage we might choose to increase (may be by doubling or some other heuristic) the size of the stack. We also want to handle the

*under-flows*i.e. if the number of elements in the stack is too small we might want to relocate the elements into a new stack ( with smaller size ). In general the dynamic data structures have a parameter called the

*load factor*and our aim is to maintain that. One simple way to maintain this is to handle under-flows and over-flows on demand. Unfortunately this will not give us a amortized cost per operation on the stack. However we can still get amortized cost by avoiding this on demand expansion and compaction.

Let denote the number of elements present on the stack after operations (including *push* and *pop*).
Let denote the allocated size of the stack after operations. We Define a potential energy function
as follows.

Clearly . The amortized cost of the

*push*operation which does not require an expansion of the stack is as follows.

The amortized cost of the

*push*operation which requires doubling of the array is as follows.

The amortized cost of the

*pop*

From the above we can see that that amortized cost of all the operations is when we use the doubling heuristic for the stack.

## (b)

Let the*load factor*and let . We use the following heuristic to handle

*expansion*and

*compaction*of the array.

"When (i.e. the array is full) increase the size of the array by times. When (i.e. the array about to under flow) reduce the size of the array by half ()".

We define the following potential function and finally show that the amortized complexity of each of
the operations *push*, *pop* is .

We now prove that the amortized cost of each operation is bounded by a constant. From the
previous problem (since the potential function is same as the previous problem when
)
we can observe that *push* operation when (*expansion*) has an amortized cost of
. We can also observe that whenever expansion does not occur the amortized cost of the push operation
is . So we will concentrate on the other possible situations. We use the notation to
indicate the load factor of the array after operations on the array.

##
Amortized cost of *push* when

##
Amortized cost of *push* when
,

##
Amortized cost of *pop* when

##
Amortized cost of *pop* when

##
Amortized cost of *pop* when
and

##
Amortized cost of *pop* when
with *compaction*

If the operation is a *pop*and we find that the load factor then we apply

*compaction*. Compaction reduces the size of the allocated array by . So after compaction . The amortized cost of the

*pop*and compaction is as follows.

We have proved that the amortized cost of both *push* and *pop* with all possible values
of the *load factor* to be .

## No comments:

Post a Comment