Amortized Analysis
Amortized analysis bounds the average cost per operation over a sequence of operations, even when individual operations are occasionally expensive.
Purpose
To analyze the average performance of a data structure over a sequence of operations, such as dynamic array resizing.
Mechanism
Three methods: aggregate analysis (total cost / number of operations), the accounting method (charging cheap operations extra to subsidize expensive ones), and the potential method (a potential function Φ measures state complexity). Dynamic array insertion is amortized O(1).
Use cases
- Data structure analysis
- Performance guarantees
- Algorithm design