Amortized complexity
In short: Amortized complexity is the average cost of an operation over a long sequence: appending to a dynamic array sometimes copies everything, but because the array grows by a factor (such as ×2), it is O(1) on average.
Problem
The import that copies everything
The shop imports the orders from an old system one by one. Someone wrote the import so that with every order the array gets one place bigger:
def import_orders(n): orders = [] copies = 0 for i in range(n): copies += len(orders) orders = orders + [100000 + i] return copiesIt looks harmless: one line per order. But every new array is a copy of the old one plus one place. The program counts the copies:
for n in [1000, 10000]: print(f"{n} orders: {import_orders(n)} copies")1000 orders: 499500 copies10000 orders: 49995000 copiesWith 10 times more orders there are 100 times more copies. With 100 000 orders there are 4 999 950 000, and the import, which takes a blink in the test, now runs for minutes. Yet list.append on the same 100 000 orders finishes at once, although it too sometimes copies the whole array. How?
The idea
The list does not grow by one place
Inside, a list is an array with more places than elements. When it fills up, it makes a new, bigger array and copies everything into it:
cart = ["Bread", "Milk", "Coffee", "Butter"]cart.append("Cheese")cart.remove("Milk")print(cart)print("Items:", len(cart))Step by step, in words
- cart points to a list object. Inside there is an ob_size counter and an ob_item array with 4 places.
- The items from the code fill the places one by one. The array is full: 4 of 4.
- There is no room. append allocates an array with 8 places, and the elements go into it.
- ob_item now points to the new array. "Cheese" goes into the first free place.
- remove removes "Milk", and everything after it moves one place to the left. No hole is left.
- From the outside you see only a list of four items. CPython decides how many places it has inside: the language does not promise it.
The secret is how much bigger the new array is. If it has one more place, every addition after the full array copies everything, like the import above. If it is twice as big, the next copy comes only after as many additions again.
See it
Your own array that doubles
Here is the same mechanism written by hand, with a counter of the copies. The array starts with one place:
class OrderList: def __init__(self): self.items = [None] self.size = 0 self.copies = 0
def add(self, order): if self.size == len(self.items): bigger = [None] * (len(self.items) * 2) for i in range(self.size): bigger[i] = self.items[i] self.copies += 1 self.items = bigger self.items[self.size] = order self.size += 1for n in [9, 1000]: orders = OrderList() for i in range(n): orders.add(100000 + i) print(f"{n} orders: {orders.copies} copies, 2n = {2 * n}")9 orders: 15 copies, 2n = 181000 orders: 1023 copies, 2n = 2000class OrderList: def __init__(self): self.items = [None] self.size = 0 self.copies = 0
def add(self, order): if self.size == len(self.items): bigger = [None] * (len(self.items) * 2) for i in range(self.size): bigger[i] = self.items[i] self.copies += 1 self.items = bigger self.items[self.size] = order self.size += 1
orders = OrderList()for i in range(9): orders.add(100000 + i)Step by step, in words
- The array starts with one place, and size is 0. We count only the copies of old elements.
- The first order: there is room, add writes it. Copies: 0.
- The second: the array is full. A new array with 2 places, and the old order is copied into it: 1 copy.
- The third: full again, 4 places and 2 copies. The fourth goes in without copying.
- The fifth copies 4, the ninth 8. The copies grow, but between them come more and more additions without copying.
- 9 additions, 1 + 2 + 4 + 8 = 15 copies, under 2n = 18. Spread over all additions, that is under 2 per addition: O(1) amortized.
An addition that finds the array full copies everything: 1, 2, 4, 8, 16 … But after it come as many additions without copying as it copied. The sum 1 + 2 + 4 + … + 2ᵏ is always under 2 · 2ᵏ, and the last copy 2ᵏ is under n. So the copies are under 2n, however big n is.
The idea
Amortized complexity
One addition can cost O(n): the one that copies everything. But n additions cost under 3n operations in total: n writes and under 2n copies. Divided by n, that is under 3 per addition: O(1).
The cost spread over a whole sequence of operations is called amortized complexity. Adding at the end of a list is O(1) amortized.
This is not "on average for a random input". The promise holds for every sequence of additions, with no luck: the expensive ones are rare, and always that rare.
Try it
Predict the output
Five orders in an array that starts with one place and doubles. How many copies?
class OrderList: def __init__(self): self.items = [None] self.size = 0 self.copies = 0
def add(self, order): if self.size == len(self.items): bigger = [None] * (len(self.items) * 2) for i in range(self.size): bigger[i] = self.items[i] self.copies += 1 self.items = bigger self.items[self.size] = order self.size += 1
for n in [5]: orders = OrderList() for i in range(n): orders.add(100000 + i) print(f"{n} orders: {orders.copies} copies")See it
One place more: O(n²)
The same class, except that the new array has one more place:
bigger = [None] * (len(self.items) + 1)for n in [9, 1000]: orders = OrderList() for i in range(n): orders.add(100000 + i) print(f"{n} orders: {orders.copies} copies")9 orders: 36 copies1000 orders: 499500 copiesWith 1000 orders doubling copies 1023 times, and growing by one place 499 500 times: 1 + 2 + … + 999. Run both growths and look at the curves. We count only the copies:
- Growth ×2: copies
O(n) - Growth +1: copies
O(n²)
| Algorithm | n = 10 | n = 1,000 | n = 100,000 |
|---|---|---|---|
| Growth ×2: copies | 15 | 1,023 | 131,071 |
| Growth +1: copies | 45 | 499,500 | ≈ 4,995,000,000 |
Doubling grows like a straight line: O(n) in total, O(1) per addition. Growing by one place grows like a parabola: O(n²) in total, O(n) per addition.
Try it
Fill in
How many places does the new array have, so that adding is O(1) amortized?
if self.size == len(self.items):
bigger = [None] * ()The new array is twice as big as the old one. So the next growth comes only after as many additions again as there are elements now.
Try it
Find the bug
A colleague replaced the doubling "so it does not waste memory". With 1000 orders the test passes quickly, and the nightly import of 100 000 drags on:
for n in [1000, 100000]: orders = OrderList() for i in range(n): orders.add(100000 + i) print(f"{n} orders: {orders.copies} copies")1000 orders: 4510 copies100000 orders: 49951000 copiesWith 100 times more orders there are 10 000 times more copies. Which line is the bug on?
Pick the line with the bug.
The array grows by 100 places at a time. That postpones the growth, but does not make it rare: every 100 additions comes a copy of everything so far, and the sum is still quadratic, about n²/200. The growth must be a multiplication (×2, ×1.5), not an addition, however big the added number.
The idea
How each language grows
No language doubles exactly, but every one multiplies:
-
Java
ArrayList: ×1.5; -
C#
List<T>: ×2; - Python (CPython 3.12): the new size is n + n/8 + 6, rounded down to a multiple of 4. That is about ×1.125. The language does not promise it; CPython decides.
- JavaScript (V8): about ×1.5.
Any factor above 1 gives O(1) amortized. The smaller it is, the more copies (under 3n for ×1.5, under 9n for ×1.125) and the fewer empty places after a growth. The choice is a trade between time and memory, as in the lesson "Space complexity".
How many places the list has at every growth, for 1000 additions:
import sys
def places(items): return (sys.getsizeof(items) - sys.getsizeof([])) // 8
orders = []seen = []for i in range(1000): orders.append(100000 + i) if not seen or seen[-1] != places(orders): seen.append(places(orders))print("The places at every growth:", " ".join(str(p) for p in seen))The places at every growth: 4 8 16 24 32 40 52 64 76 92 108 128 148 172 200 232 268 308 352 400 456 520 592 672 760 860 972 1100More precisely, if you are curious
O(1) amortized does not mean every addition is fast. The addition that copies is O(n). In most programs you do not notice it, but in a program that must not stop (a till, a game, audio processing), one addition of the millionth element may be the slow one. If you know how many elements there will be, set the places up front: [None] * n. Then the list never copies.
[None] * n makes a list of n None elements, and then you write by index, not with append.The bound for ×2 has another form too: every addition "pays" 2 copies in advance and saves them. When the array with k elements fills up, the last k/2 additions have saved k, exactly what the copy costs. The savings never go negative, so the sum is under 2n.
Exercise
Growth as in Java
Solve the task in your editor.
Growth by half. Change the growth of OrderList so that the new array has the old places plus half (at least one place more). Count the copies for 1000 and for 100 000 orders. Are they under 2n? And under 3n?
1000 orders: 2137 copies, 2n = 2000100000 orders: 276521 copies, 2n = 200000More tasks
- Removing from the end. Add
removeLast. When should the array shrink, so that removing is O(1) amortized too? Try "by half, when it is half full" and alternate adding and removing exactly at the boundary. Then try "by half, when it is a quarter full". Why is the second O(1) amortized and the first not? - How many places it wastes. After 1000 additions with doubling, how many places are empty? And with growth ×1.5?
Test