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
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.
AlgorithmsPart of Computer Science Notes
Series on Algorithms
Algorithm Practice and Writeups
Flags · Template:AlgorithmsFlag · e