🧮 Amortized Analysis Calculator
Model a dynamic array that grows by doubling and watch the aggregate method turn a sequence of appends — some cheap, some expensive — into a single constant amortized cost per operation.
📊 Aggregate Method — Dynamic Array
🧮 Aggregate cost over 8 appends
| Resize # | At append | Elements copied | New capacity |
|---|---|---|---|
| 1 | 2 | 1 | 2 |
| 2 | 3 | 2 | 4 |
| 3 | 5 | 4 | 8 |
What is an Amortized Analysis Calculator?
It makes the aggregate method concrete. Choose how many elements you append and the factor by which the array grows when it fills, and the calculator replays the whole sequence: it counts every unit insert, logs each resize and the elements it copies, sums the total, and divides by n to show the amortized cost per operation.
This is the canonical example for teaching amortized cost, and the numbers are striking — the total for n appends with doubling comes to roughly 2n, so the per-append cost stays a small constant no matter how large n gets. Use it to build intuition for why languages back their lists and vectors with doubling arrays, and to see how the growth factor trades wasted memory against copy work.
❓ Frequently Asked Questions
What is amortized analysis?
Amortized analysis measures the average cost of an operation over a worst-case sequence of operations, rather than the worst cost of any single operation. It captures the fact that an occasionally expensive step (like resizing an array) is paid for by many cheap steps around it, giving a fairer per-operation cost.
How does the aggregate method work here?
The aggregate method sums the total cost of a sequence of n operations, then divides by n. For a dynamic array, each of the n appends costs 1, and each resize copies the current elements into a larger backing store. This tool adds those copy costs to the n unit costs and divides by n to get the amortized cost per append.
Why is appending to a dynamic array O(1) amortized?
With doubling, the total copy work across n appends is 1 + 2 + 4 + … which sums to less than 2n, so the total cost is under 3n and the amortized cost per append is a small constant — O(1) — even though an individual append that triggers a resize costs O(n). Enter n = 8, growth 2 to see the total 15 (which is 2n − 1) and an amortized cost under 2.
Does the growth factor matter?
Yes. Any growth factor greater than 1 keeps appends O(1) amortized, but the constant changes: a larger factor means fewer, larger resizes (fewer copies overall, more wasted capacity), while a smaller factor closer to 1 means many small resizes and more total copying. Vary the growth factor here to watch the number of resizes and the amortized cost shift.