Home | | Programming and Data Structure II | Amortized analysis

# Amortized analysis

Amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations.

AMORTIZED ANALYSIS:

Amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations.

â€˘         Not just consider one operation, but a sequence of operations on a given data structure.

â€˘         Average cost over a sequence of operations.

â€˘         Probabilistic analysis:

â€“ Average case running time: average over all possible inputs for one algorithm (operation).

â€“   If using probability, called expected running time.

â€˘         Amortized analysis:

â€“   No involvement of probability

â€“ Average performance on a sequence of operations, even some operation is expensive.

â€“ Guarantee average performance of each operation among the sequence in worst case.

Three Methods of Amortized Analysis:

â€˘         Aggregate analysis:

â€“   Total cost of n operations/n,

â€˘   Accounting method:

â€“ Assign each type of operation an (different) amortized cost overcharge some operations, store the overcharge as credit on specific objects, then use the credit for compensation for some later operations.

â€˘         Potential method:

â€“   Same as accounting method.

â€“   But store the credit as â€śpotential energyâ€ť and as a whole.

Example for amortized analysis:

â€˘         Stack operations:

â€“   PUSH(S,x), O(1)

â€“   POP(S),  O(1)

â€“   MULTIPOP(S,k), min(s,k)

while not STACK-EMPTY(S) and k>0 do POP(S)

k=k-1

â€˘         Let us consider a sequence of n PUSH, POP, MULTIPOP.

â€“ The worst case cost for MULTIPOP in the sequence is O(n), since the stack size is at most n.

â€“   Thus the cost of the sequence is O(n2). Correct, but not tight.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data structures : Advanced Non-Linear Data Structures : Amortized analysis |