1

This question already has an answer here:

"amortize" mean

reduce or extinguish (a debt) by money regularly put aside.

i.e. to pay off of debt with a fixed repayment schedule in regular installments over a period of time.

In amortized analysis of algorithms, does "amortize" also mean to reduce something by something else regularly put aside?

marked as duplicate by user40980, user7043, GlenH7, user22815, durron597 Sep 11 '15 at 15:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

7

Amortized worst-case analysis is called so because of its analogy to finance.

Amortized worst-case analysis looks at multiple successive operations on a data structure instead of treating every operation individually. The idea is that, unless you are developing a hard-realtime system, you will be more interested in how the system performs overall than how it performs at every single instant.

For example, think about how you would implement a dynamic (i.e. resizable) array: you would guess a suitable size for the array, then start adding elements to it one-by-one. At some time, the array is full, and when you add a new element, you have to create a new, bigger, array and copy all the existing elements over to the new array. That's an O(n) operation. So, the worst-case for adding an element to a dynamic array is O(n). That's clearly undesirable, a static array has O(1), and we don't want our dynamic arrays to be significantly slower than static arrays.

So, the worst-case is O(n). But … how often does that worst-case occur? Well, it turns out that if we do the resizing right, in particular, if we resize exponentially (e.g. double the size everytime the array is full), resizing happens rather rarely.

Intuitively, resizing needs to occur less than every O(n) operations, and it takes O(n) time, so overall the array seems to behave as if it had O(1) add time, even though it doesn't. Only the one call which actually ends up triggering the resize will be slow, all others will be fast, and there are far more fast calls than slow calls (in fact, there are more than O(n) times more fast calls than slow calls).

If you want all the gory details for how exactly amortized worst-case analysis is defined, how to perform it, and how to prove that dynamic arrays have O(1) amortized worst-case add, you should consult an algorithms textbook.

But the intuition is this: just like taking on a loan to buy a big machine amortizes itself over time, because the bigger machine means you make more money which allows you to pay back the loan, allocating a larger array and copying all the elements over amortizes itself because there will be a large number of "fast adds" that allow you to "pay back" the time penalty you took on that one slow add. That's why it's called "amortized analysis", because it allows you to "borrow time" for infrequent slow operations and pay that time back with frequent fast operations.

Note that this is still different from expected worst-case analysis and average-case analysis. Those have probability distributions and random variables, but amortized worst-case analysis is still deterministic worst-case, it just looks at the "bigger picture" of how a data structure is used over time.

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