Amortized Analysis
← Back to Time Complexity
A method that averages the time required for a sequence of operations over the entire sequence, even though individual operations may be expensive. Classic example: dynamic array resizing has O(1) amortized insert despite occasional O(n) resizes.
Key Properties
Related
- Big-O Notation (per-operation analysis)