Amortized analysis
Show that an occasional expensive step still gives constant average cost per operation.
On this page
Classes and growth rates.
- Show that an occasional expensive step still gives constant average cost per operation.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Amortized analysis bounds the average cost of an operation over a worst-case sequence of operations. It is different from average-case analysis: no probability or random input is involved. It guarantees that any sequence of n operations costs at most n times the amortized bound in total, even though an individual operation can be expensive.
A dynamic array shows the idea. Appending usually writes one slot, but when the array is full it allocates a larger block and copies every element. If the capacity doubles each time, the copy costs are 1, 2, 4, 8, ... and their sum for n appends is less than 2n. Total work is at most about 3n, so each append has amortized cost O(1). Aggregate analysis, as used here, simply divides the total by n; the accounting and potential methods reach the same result by assigning credits to cheap operations.
Growth by a constant amount instead of a constant factor does not work: copying every k appends gives Θ(n²) total work. CPython's list over-allocates by a smaller proportional factor than 2, but because it is proportional the same argument applies.
Code example
class DynamicArray:
def __init__(self):
self.capacity = 1
self.size = 0
self.copies = 0
def append(self):
if self.size == self.capacity:
self.capacity *= 2
self.copies += self.size
self.size += 1
array = DynamicArray()
for _ in range(16):
array.append()
print(array.size, array.capacity, array.copies)
print(array.copies / array.size)
assert array.copies < 2 * array.size16 16 15 0.9375
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
class DynamicArray: def __init__(self): self.capacity = 1 self.size = 0 self.copies = 0 def append(self): if self.size == self.capacity: self.capacity *= 2 self.copies += self.size self.size += 1 array = DynamicArray()for _ in range(16): array.append()print(array.size, array.capacity, array.copies)print(array.copies / array.size)assert array.copies < 2 * array.sizeFollow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| A full array doubles and copies every element. The copies happen at sizes 1, 2, 4, and 8. | copies = 1 + 2 + 4 + 8 | — | |
| Every append stores one element; resizing adds extra work only occasionally. | copies = 1 + 2 + 4 + 8 | — | |
| After 16 appends the capacity is 16 and 15 element copies were needed in total. | size = 16, capacity = 16, copies = 15 | 16 16 15 | |
| Fewer than one copy per append on average: the cost is spread across the sequence. | size = 16, capacity = 16, copies = 15 | 16 16 15 0.9375 |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
n appends cost Θ(n) in total, so each append is amortized O(1). The array uses O(n) space, at most a constant factor over the stored elements.
- Amortized O(1) does not mean every append is O(1). A single append that triggers a resize is Θ(n).
- Amortized cost is not average-case cost. It holds for the worst possible sequence of operations, with no assumption about the input distribution.
- Growing the capacity by a fixed amount, such as 10 slots, makes the total quadratic. The growth must be proportional.
Try it yourself
Change the loop to 17 appends and predict capacity and copies.
Reveal answer and reasoning
The 17th append finds the array full at size 16, so the capacity becomes 32 and 16 more elements are copied: capacity 32, copies 31.