6
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
13
$\begingroup$

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.
Improve this answer
$\endgroup$
4
  • $\begingroup$ I must admit I couldn't understand your answer on the first go. But eventually I did though. $\endgroup$
    – Sid
    Commented Nov 26, 2012 at 9:26
  • $\begingroup$ @Sid Is there something in particular I can/should clarify? $\endgroup$
    – Raphael
    Commented Nov 26, 2012 at 11:43
  • $\begingroup$ I was initially confused with the 2nd paragraph, where you said we execute lots and lots of operations. I got confused there. I don't know if I am right, can we write that we execute an operation lots of times and get the average time the operation takes? $\endgroup$
    – Sid
    Commented Nov 26, 2012 at 18:08
  • $\begingroup$ @Sid Depends. 1) There may be more than one operation involved. For example, when analysing UNION/FIND data structures, you usually consider a sequence of $n$ UNION and $m$ FIND operations. 2) You get the average time if you can find the exact runtime of the sequence. Otherwise, you get an upper bound. I would stear clear of the word "average" nevertheless in order to avoid confusion with average-case analysis. $\endgroup$
    – Raphael
    Commented Nov 26, 2012 at 19:42
10
$\begingroup$

Consider the std::vector container from the STL, together with it's appending operation, push_back(). This operation has amortized running time $O(1)$.

Why? std::vector implemented as an array which can dynamically grow, if more space is needed. The strategy it uses for resizing is simple: it doubles it's size whenever you try to push_back a new element to a vectorthat is full. After that resizing operation, appending elements can be done in constant time: they are just inserted into the array "behind" the last element.

So, if you are growing a std::vector object by calling push_back very often, fewer and fewer growing operations need to be done, because of that exponential growing strategy: Eventually, the likelihood that your insertion operation is running in constant time converges to one.

Long story short: you do amortized analysis to determine the "average" complexity of your algorithm, given the case that it performs "usually" well, but not always. Like e.g. inserting elements at the end of a std::vector.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.