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

Taught in

References