What is Amortized analysis ?

Amortized analysis method is used for analyzing the given algorithms complexity especially in time or memory, it takes to execute. Instead of per algorithm it stated worst case run time per operation. In data structure it is most commonly used scenario which have state that persists between operations. Three methods are useful to perform amortized analysis - the aggregate method, the accounting method and the potential method. Among these which one used is depends on which is the most convenient for particular situation. To examine three methods, we shall used Stack example with additional operation MULTIPOP, which pops several objects at ones.

Aggregate Method
In aggregate method of amortized analysis we determine that for sequence of n operations it takes worst case time T(n) in total. Therefore in the worst case the amortized cost or the average cost per operation is T(n)/n. Still these cost is applied to all operations even when there are several types of operations in the sequence. Consider a stack that has been augmented with new operation.

PUSH (S, a ) pushes object a onto stack S
POP(S) pops the top of stack S and returns the popped object.

Each operations runs in O(1) time. Suppose the cost of each is 1, therefore the total cost of n PUSH and POP is n. The actual running time for n operations is Θ(n). If MULTIPOP (S, p) operation is add which removes the p top objects of stack S or if stack contains less than p objects it pops the entire stack. If there are no objects currently on stack then the operation STACK-EMPTY returns TRUE otherwise FALSE.
MULTIPOP (S, p)

1.       while not STACK-EMPTY (S) and p ≠ 0
2.       do POP (S)
3.       p = p - 1

So the actual running time of MULTIPOP (S, p) on stack of S object is linear in the number of POP operations actually executed, and thus it suffices to analyze MULTIPOP in terms of the abstract costs of 1 each for PUSH and POP. The while loop’s number of iterations is the number min(S, p) of objects popped off the stack. One call is made to pop for each iteration in line 2. So the total cost of MULTIPOP is min(s, p), and the actual running time is a linear function of this cost. On an initially empty stack, if we analyze sequence of n PUSH, POP, and MULTIPOP operations, worst-case cost of a MULTIPOP operation in the sequence is O(n), since the stack size is at most n. Thus a sequence of n operations costs O(n2). With aggregate method of amortized analysis we get better upper bound of entire sequence of n operations. Each object can be popped at most once for each time it is pushed. Thus on non empty stack the number of times that pop can be called including calls within MULTIPOP, is at most the number of PUSH operations, which is at most n. For any value of n, any sequence of n PUSH, POP, and MULTIPOP operations takes a total of O(n) time. The amortized cost of an operation is the average: O(n)/n = O(1).

Accounting Method

In accounting method we allocate different charges to different operations. Some operations charged more or less than their actual cost. The amount we charged on operation is known as amortized cost. When an operation's amortized cost exceeds its actual cost, the difference is assigned to specific objects in the data structure as credit. This credit is used later on for the operations whose amortized cost less than their actual cost. As we simply observed the amortized cost of an operation as being split between its actual cost and credit that is either deposited or used up. This is the difference of accounting method from aggregate method where all operations have the same amortized cost.  

Lets consider our stack example as the actual cost of operation were 

PUSH              1 , 

POP                 1 ,
MULTIPOP    min (p,s)

Let assign amortized costs
PUSH              2
POP                 0
MULTIPOP     0

The actual cost of MULTIPOP operation is variable but the amortized cost is constant (0). Here all three amortized cost is O(1) Thus, for any sequence of n PUSH, POP, and MULTIPOP operations, the total amortized cost is an upper bound on the total actual cost. Since the total amortized cost is O(n), so is the total actual cost.

Potential Method

Potential method of amortized analysis represents the prepaid work as "potential energy" or just "potential," instead of credit stored with specific objects in the data structure. This potential energy is release to pay for future work. For example again we consider our stack operations PUSH, POP and MULTIPOP. Assume the number of objects in the stack is equal to the potential function Φ on a stack. For the empty stack D_0, we have Φ (D₀) = 0. Since the number of objects in the stack is never negative, the stack D_i that results after the i^th operation has non negative potential. Φ (D_i) ≥ 0 = Φ (D₀). Total amortized cost of n operations with respect to Φ therefore represents an upper bound on the actual cost. Let us now compute the amortized costs of the various stack operations. If the i^th operation on a stack containing s objects is a PUSH operation, then the potential difference is

                                                          Φ(D_i) - Φ(D_i  -1)  =  (s + 1 ) - s =  1.

So the amortized cost of this PUSH operation is

Suppose that the ith operation on the stack is MULTIPOP (s,p) and that p' = min(p,s) objects are popped off the stack. The actual cost of the operation is p', and the potential difference is Φ(D_i) - Φ(D_i  -1)  = -p'. Thus the amortized cost of the MULTIPOP operation is 

Similarly, the amortized cost of an ordinary POP operation is 0. The amortized cost of each of the three operations is O(1), and thus the total amortized cost of a sequence of n operations is O(n). Since we have (Di ≥ D₀), the total amortized cost of n operations is an upper bound on the total actual cost. The worst case of n operations is therefore O(n).