Amortized Analysis

The average cost per operation over a worst-case sequence of operations.

Intermediate

Appending to a dynamic array is occasionally $O(n)$ (resize) but $O(1)$ amortized because capacity doubles.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)