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

Aggregate Method

The simplest way of thinking about amortization is using the aggregate method: to compute the amortized cost per operation, we sum up the time for k operations, and divide by k.

Amortized cost per operation = ( total cost of k operations ) / ( k )

The downside is, mixing different operations makes things more complicated.

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