It's all about self learning.

Amortized Algorithm

Amortized Algorithm and Types of Amortized Algorithm
6 November, 2016     

This means finding average running time per operation over a worst case sequence of operations.

This analysis shows that average cost/time of an operation is small even though cost of sum of the operation is large.

The difference between amortized cost/time & average case is that in amortized we are averaging over a sequence of inputs and operation and in the case of average we just averaging over various inputs.

It has basically three parts:-
                 a) Aggregate analysis
                 b) Accounting method
                 c) Potential method

Aggregate Analysis:- In this type of analysis, we have a sequence of ‘n’ operations and total worst case time taken by these operations is T(n).

But in worst case, the average cost or amortized cost, per operation is therefore T(n)/n. This amortized cost applies to each operation, even when there  are several type of operation in the sequence.

e.g.  Consider an example of stack operation which are  push and pop.The routines for them are:-

              If the stack to p is not empty then
                  push = item

        T(n) = o(1)
                    If stack is empty
                        pop = item
          T(n) = o(1)

Amortize time = (o(1)+o(1))/2 = o(1)

In case we have to pop ‘n’ element then amortized time is o(n).

 e.g. Write a function of performing multiple pop operation.

Ans.  Algo:-
           Algo multipop(st,k)  //where k is No. of element

              While(st!=empty and k!=0)do


In actual cost we have two operations push and pop. Each time when we execute these operation we have to call it string data in STACK.

In amortized cost we assign Push = 2 when we push the item into empty stack it’s value become Push = 1. Then we no need to assign the value to pop because the data stored in stack is prepayment for the cost of popping function.When we execute pop operation,we charge nothing. Thus amortized cost is an upper bound on the Total actual cost. Hence the amortized cost is still O(1).

Multiple Choice Questions