Amortized Analysis

Definition: The amortized cost per operation for a sequence of $n$ operations is the total cost of the operations divided by $n$.

  • An analysis of the worst case cost of a sequence of operations is called an amortized analysis.
  • The motivation for amortized analysis is that a worst-case-per-operation analysis can give overly pessimistic bound if the only way of having an expensive operation is to have a lot of cheap ones before it. (The cost is in fact not that high!)
  • Note that this is different from our usual notion of “average case analysis”: we are not making any assumptions about the inputs being chosen at random, we are just averaging over time.

General Approach

Most of the art of doing an amortized analysis is in

  • (1) Choosing the right potential function.
  • (2) Prove that with the chosen potential function, the amortized costs of the operations satisfy the desired bounds.
  • (3) Bound the quantity $Φ(s_0) − Φ(s_n)$ appropriately.

Key ideas

  • Amortized analysis is an upper bound: it's the average performance of each operation in the worst case.
  • Amortized analysis is concerned with the overall cost of a sequence of operations. It does not say anything about the cost of a specific operation in that sequence.
  • Amortized analysis is concerned with the overall cost of arbitrary sequences. An amortized bound will hold regardless of the specific sequence
  • The two points above imply that both amortized and worst case bounds should be understood when choosing an algorithm to use in practice. Because an amortized bound says nothing about the cost of individual operations, it may be possible that one operation in the sequence requires a huge cost. Practical systems in which it is important that all operations have low and/or comparable costs may require an algorithm with a worse amortized cost but a better worst case peroperation bound.
  • Amortized analysis can be understood to take advantage of the fact that some expensive operations may “pay” for future operations by somehow limiting the number or cost of expensive operations that can happen in the near future.
  • If good amortized cost is a goal, an algorithm may be designed to explicitly perform this “clean up” during expensive operations!
  • The key to performing amortized analysis is picking a good “credit” or “potential” function that captures how operations with different actual costs affect a data structure and allows the desired bounds to be shown.
  • Amortized analysis is closely related to competitive analysis, which involves comparing the worst case performance of an online algorithm to the performance of an optimal offline algorithm on the same data.
  • Amortized analysis differs from average-case analysis in that probability is not involved; an amortized analysis guarantees the average performance of each operation in the worst case.

Aggregate analysis

  • we show that for all $n$, a sequence of $n$ operations takes worst-case time $T(n)$ in total. In the worst case, the average cost, or amortized cost, per operation is therefore $T(n)/n$.
  • All operations are assigned the same amortized cost, even if they are of different types

Banker’s View of Amortization (The accounting method)

  • Make a rule that says how much money must be kept in the bank as a function of the state of the data structure.
  • Then a bound is obtained on how much money is required to pay for an operation and maintain the appropriate amount of money in the bank.
  • It is very important in this analysis to prove that the bank account doesn’t go negative.

Physicist’s View of Amortization (The potential method)

Definition: A potential function is a function of the state of a system, that generally should be non-negative and start at 0, and is used to smooth out analysis of some algorithm or process.

  • A potential function $Φ(s)$ is a mapping from data state structure states to the reals.
  • Consider a sequence of $n$ operations $σ_1, σ_2, ..., σ_n$, σn the data structure. Let the sequence of states through which the data structure passes be $s_0, s_1, ..., s_n$.
  • Notice that operation $σi$ changes the state from $s{i−1}$ to $s_i$.

  • Let the cost of operation $σi$ be $c_i$. Define the amortized cost $ac_i$ of operation $σ_i$ by the following formula: $ac_i = c_i + Φ(s_i) − Φ(s{i−1})$

    • $\sum{i}^{n}ac_i = \sum{i}^{n}(ci + Φ(s_i) − Φ(s{i−1})) = \sum_{i}^{n}c_i + Φ(s_n) − Φ(s_0)$

    • $\sum{i}^{n}c_i \leq \sum{i}^{n}ac_i$ if $Φ(s_0) \leq Φ(s_n)$

if we can bound the amortized cost of each of the operations, and the final potential is at least as large as the initial potential, then the bound we obtained for the amortized cost applies to the actual cost.

results matching ""

    No results matching ""