6.046 amortization

Algorithms › 6.046 algorithms design

We have already known amortization in array resizing and hashing with chaining.

Amortized bound: sum(amortized cost) >= sum(actual cost)

Ex: 2-3 tree, O(1) amortized cost per create, O(lg n*) amortized cost per insert, and 0 amortized cost per delete.

  • n* is the maximum size of 2-3 tree.
  • 0 amortized cost per delete: can’t delete without inserting first.

amortized analysis techniques

  1. aggregate method

    amortized cost per operation = total cost of k operations / k

  2. accounting method

    for each operation:

    ​ Store credit: amortized cost > actual cost

    ​ pay for it: amortized cost < actual cost

    Example

    • table doubling

    • 2-3 tree

  3. charging method

    amortized cost of an operation = actual cost of this operation - total cost charged to past operations + total cost charged by future operations

    Example

    • table doubling and halving
    • Free deletion in 2-3 trees

  4. potential method

    Example:

    • binary counter
    • insert in 2-3 tree
    • Insert and delete in 2-5 tree

union-find

Problem: how can a simple doubly linked list improve to support fast search and fast union? how this method is different from what is in cs61b disjoint set course?