What Is Amortized Analysis? Cost Across a Sequence of Operations
Amortized analysis bounds the total cost of a sequence and divides that cost across its operations. It explains why an occasional O(n) dynamic-array resize can coexist with O(1) amortized append.
Amortized analysis studies the total cost of a sequence of operations. One operation may be expensive, but if expensive operations are rare and create room for many cheap operations, the cost per operation can still have a small guaranteed bound across the sequence.
This is not average-case analysis. Average-case analysis depends on a distribution of possible inputs. An amortized bound covers every operation sequence allowed by the model, without assuming that inputs are random.
Dynamic-array append
Imagine an array whose capacity doubles whenever it becomes full. Most appends write one value into unused storage, which costs O(1). A resize append allocates a larger block and copies every existing value, so that individual operation costs O(n).
The copies do not happen on every append. If capacities grow through 1, 2, 4, 8, and 16, the resize copies move 1, then 2, then 4, then 8 values. Before 16 values have been appended, fewer than 16 old values were copied in total.
The geometric sum stays below a constant multiple of the number of appends. Therefore n appends take O(n) total time, and each append costs O(1) amortized time.
A runnable model
The small class below counts writes while capacity doubles. It models the cost argument without depending on a JavaScript engine's internal array representation.
Press Run to execute this example. Use console.log to print a value.
Sixteen appends perform sixteen writes for the new values and fifteen copy writes during growth. One append was expensive, but the complete sequence used fewer than two writes per append on average. The bound follows the growth policy, not luck.
Aggregate and charging views
The aggregate method adds the costs of all operations, then divides by the number of operations. For doubling storage, total writes across n appends are O(n), so the amortized cost is O(1).
The accounting method assigns a slightly larger constant charge to each cheap append. The unused part of that charge pays for copying the value during a future resize. This is a proof device; the program does not store actual credits.
Both views establish the same sequence-wide guarantee.
Monotonic structures
Amortized analysis also explains why a monotonic stack or deque can be linear. One incoming value may trigger many pops, so one iteration can look expensive. Across the whole run, however, each index is pushed once and popped at most once.
The total number of stack or deque operations is O(n). The nested while loop does not make the complete algorithm O(n²).
Cost
For dynamic-array append, one operation is O(n) in the resize worst case, while a sequence of n appends is O(n) total and O(1) amortized per append. The backing storage is O(n).
For a monotonic stack, one iteration can pop O(n) entries, but all iterations together perform O(n) pushes and pops. Auxiliary space is O(n) in the worst case.
Always state which guarantee you mean: worst-case per operation, expected, or amortized. They answer different questions.
In the course
Arrays use amortized append. Monotonic stacks and deques use the “each item enters and leaves at most once” argument. These cases teach the same habit: count an operation across the whole sequence instead of multiplying the most expensive single iteration by the number of iterations.
Common mistakes
Do not call amortized cost an average over random inputs. No probability is required.
Do not claim that every append is O(1). A resize append can be linear even though the amortized cost is constant.
Do not inspect only the most expensive iteration of a monotonic-stack loop. Count how many times each index can be pushed and popped over the complete run.