amortised analysis
Measuring the average cost per operation over a long sequence of operations, so rare expensive steps are spread across many cheap ones.
In more detail
Appending to a Python list is O(1) amortised: most appends are cheap, and the occasional O(n) copy into a bigger block is paid for by all the cheap appends before it. This is a guarantee about totals, not an average over random inputs. A single append can still be slow, which matters for code with strict per-operation deadlines.
Related terms
- dynamic array — An array that grows on demand by allocating a larger block and copying the existing items across when it runs out of room.
- accounting method — A way to prove an amortised bound by charging each cheap operation a little extra "credit" that is saved to pay for later expensive ones.
- doubling strategy — Growing a full dynamic array by multiplying its capacity by a constant factor, typically two, rather than adding a fixed number of slots.
Taught in
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Arrays: Contiguous Memory And Constant-Time Access — Algorithms & Data Structures for Working Engineers
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers