Skip to main content

Amortized Complexity

Learn Amortized Complexity (Complexity, Programming Fundamentals) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

What is Amortized Complexity? Amortized complexity describes the average cost per operation over a long sequence of operations , even when a few individual operations in that sequence are much more expensive than the rest. It is NOT the same as "average case" (which is about typical input). Amortized analysis is about spreading out the cost of occasional expensive operations across many cheap ones , so the per-operation cost, averaged over the whole sequence, stays low. The textbook Java example is ArrayList.add() — most calls are O(1), but every so often the internal array is full and must be...

More lessons in Complexity