[Solved]: Advantages of amortized analysis

Problem Detail: 

I understood what amortized analysis does, but can anyone tell me what is the main purpose of this kind of analysis?

What I understood:

Let say we have 3 three operations a,b,c used 1,2 and 3 times to achieve d. Based on aggregate analysis a,b and c are used 2 times each. Is this correct?

I am trying to understand the advantages of this in CLRS but I am completely lost. For example in dynamic programming we save the answers to sub problems in tables which helps us reduce the running time(lets say from exponential to polynomial). But I am unable to get a complete picture of amortized analysis.

Asked By : Sid

Answered By : Raphael

Amortised analysis is a tool to get more useful results than "naive" worst-case analysis. Especially in the realm of advanced data structures, operations can be cheap most of the time but expensive in rare cases; worst-cases analysis yields only the latter case as characteristic of the data structure. Dynamic arrays, splay trees and some flavors of hash tables are among the more popular examples.

For many purposes, that is too pessimistic. We don't actually need that every operation is fast¹; we execute lots and lots of operations (e.g. during an algorithm) and we want the total runtime to be small. That is what amortised analysis looks at.

Be careful not to confuse amortised analysis with average-case analysis. The former is still considering the worst case; it only sums over time and spreads the cost evenly; you get for one operation its share of the worst-case total cost. On the other hand, average-case assumes a probability distribution over inputs and/or the sequence of operations, and yields the expected time per operation, which is (by definition) its share of the expected total cost.

---

1. Real-time applications are a notable exception.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6865