Search code examples
algorithmcomplexity-theorygraph-theorynp

What does the word "amortized" mean in amortized analysis of algorithms?


I obviously am familiar with the texts mentioning it is an average lower bound etc... but still wondering why the word amortized was put there ?

Why is amortize used in describing algorithm analysis ?


Solution

  • Because the computer scientists who thought up the idea were using a financial analogy.

    You amortise a significant expenditure (like building a new house) by paying for it over time (perhaps with a mortgage, which has the same root).

    Similarly, in amortised analysis of algorithms you pay for a huge and uncommon occurrence (copying an entire vector of when it gets full) by spreading its cost over subsequent operations (or previous operations in the banker's model).