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:
function importOrders(n) { let orders = []; let copies = 0; for (let i = 0; i < n; i++) { copies += orders.length; orders = [...orders, 100000 + i]; } return copies;}It 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 (const n of [1000, 10000]) { console.log(`${n} orders: ${importOrders(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 push 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:
const cart = ["Bread", "Milk", "Coffee"];cart.push("Butter");cart.splice(cart.indexOf("Milk"), 1);console.log(cart);console.log(`Items: ${cart.length}`);Step by step, in words
- cart points to an array. Inside, it has length and a separate elements array with 3 places.
- The items from the code fill the places one by one. The array is full: 3 of 3.
- There is no room. push makes an array with 22 places and copies the elements into it.
- elements now points to the new array, and nobody needs the old one. "Butter" goes into the free place.
- splice removes "Milk", and everything after it moves one place to the left. No hole is left.
- From the outside you see only an array of three items. The V8 engine 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 { constructor() { this.items = new Array(1); this.size = 0; this.copies = 0; }
add(order) { if (this.size === this.items.length) { const bigger = new Array(this.items.length * 2); for (let i = 0; i < this.size; i++) { bigger[i] = this.items[i]; this.copies++; } this.items = bigger; } this.items[this.size] = order; this.size++; }}for (const n of [9, 1000]) { const orders = new OrderList(); for (let i = 0; i < n; i++) { orders.add(100000 + i); } console.log(`${n} orders: ${orders.copies} copies, 2n = ${2 * n}`);}9 orders: 15 copies, 2n = 181000 orders: 1023 copies, 2n = 2000class OrderList { constructor() { this.items = new Array(1); this.size = 0; this.copies = 0; }
add(order) { if (this.size === this.items.length) { const bigger = new Array(this.items.length * 2); for (let i = 0; i < this.size; i++) { bigger[i] = this.items[i]; this.copies++; } this.items = bigger; } this.items[this.size] = order; this.size++; }}
const orders = new OrderList();for (let i = 0; i < 9; i++) { 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 { constructor() { this.items = new Array(1); this.size = 0; this.copies = 0; }
add(order) { if (this.size === this.items.length) { const bigger = new Array(this.items.length * 2); for (let i = 0; i < this.size; i++) { bigger[i] = this.items[i]; this.copies++; } this.items = bigger; } this.items[this.size] = order; this.size++; }}
for (const n of [5]) { const orders = new OrderList(); for (let i = 0; i < n; i++) { orders.add(100000 + i); } console.log(`${n} orders: ${orders.copies} copies`);}See it
One place more: O(n²)
The same class, except that the new array has one more place:
const bigger = new Array(this.items.length + 1);for (const n of [9, 1000]) { const orders = new OrderList(); for (let i = 0; i < n; i++) { orders.add(100000 + i); } console.log(`${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 (this.size === this.items.length) {
const bigger = new Array();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 (const n of [1000, 100000]) { const orders = new OrderList(); for (let i = 0; i < n; i++) { orders.add(100000 + i); } console.log(`${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): about ×1.125;
- JavaScript (V8 in Node and Chrome): the new size is n + n/2 + 16, about ×1.5. The language does not promise it; the engine decides.
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".
More 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: new Array(n). Then the list never copies.
new Array(n) makes an array with holes, which V8 stores more slowly than a dense one. Usually push is the better choice, and no holes are made.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