# Amortization

### From charlesreid1

# Notes

An operation takes "T(n) amortized" if k operations take 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,

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

# Flags

AlgorithmsSeries on Algorithms
Algorithms/Sort Three solid O(n log n) search algorithms: Merge Sort Algorithm Analysis/Merge Sort
Algorithms/Search
Algorithms/Combinatorics
Algorithms/Strings
Algorithm complexity
Algorithm Analysis/Matrix Multiplication
Estimation
Project Euler
· Template:AlgorithmsFlag · e |