What is amortized cost?

[jinjin12]

I hear this "armortized" cost stuff everywhere, for example, amortized cost of BST search or amortized cost of bubble sort. What does amortized mean? my teach don't explain it well.

[naraku9333]

This might help http://en.wikipedia.org/wiki/Amortized_analysis

This paper looks like it goes into more detail http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

[jinjin12]

so amortized cost is basically the average cost? or am i understand that wrong?

[Duthomhas]

No, it is a method of rating the "cost" (time and space) used by an algorithm.

Check out this FAQ section for more:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/#Big-O
(And make sure to click the links too.)