Amortized Analysis
Average cost per operation over a sequence, even when a few operations are expensive.
Complexity in Numbers: Appends to a doubling array
Append 1: room for it, one write. Cost 1, total 1, average 1.0.
Cost
- Space
- O(1)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Complexity in Numbers covers these too, in the same run.