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.

•         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(n²). Correct, but not tight.