Amortization

Notes

An operation takes "T(n) amortized" if k operations take $ \leq k \cdot T(n) $ time

k inserts take theta(k) time, so this is O(1) amortized insert

Methods for amortized analysis:

• Aggregate method - see below
• Accounting method - see Amortization/Accounting Method
• Charging method
• Potential method

Amortization of resizing:

• We already encountered amortized resizing with the Python dynamicaly-resized array data structure: Arrays/Python/DynamicArrayResizing
• We also encountered them with hash tables and dynamic resizing of hash tables: Hash_Maps/Dynamic_Resizing#Amortization

$ \sum \text{actual cost} \leq \sum \text{amortized cost} $

More General Definition

The more general way of talking about an amortized bound is saying, each operation will have some particular cost that we assign it (amortized cost). We are then only required to preserve the sum of these costs. That is,

$ \sum \mbox{actual cost} \leq \sum \mbox{amortized cost} $

If we know that the amortized cost is at most constant, then we know that the actual cost is at most constant. This abstracts away costs of individual operations, only focusing on the overall cost.

Links

See https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_lec05.pdf