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
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.
"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.
We have proved that the amortized cost of both push and pop with all possible values of the load factor to be .