amortized cost term
average cost per operation over a sequence
Some operations are expensive but rare. Dynamic array push: usually O(1), occasionally O(n) when resizing. Amortized: O(1). Lets you reason about realistic cost.
average cost per operation over a sequence
Some operations are expensive but rare. Dynamic array push: usually O(1), occasionally O(n) when resizing. Amortized: O(1). Lets you reason about realistic cost.