Dynamic table (amortized analysis)

An array that doubles whenever it fills up; the copies are sometimes expensive, but the amortized cost per insert is at most 3.

We want an array we can keep inserting into. When the table is full, make one twice as big and copy every item into it.

Read the full explanation ↓

Time: O(1) amortized per insert
Space: O(n)
CLRS, section 16.4

Input:

n=9PDF export

9 inserts; the table grows at inserts 2, 3, 5 and 9, needing 1+2+4+8 = 15 copies. The total cost is 24, under 3 × 9.

def dynamic_table(items):
capacity = 1
table = [None]
size = 0
copies = 0
for item in items:
if size == capacity:
capacity = 2 * capacity
bigger = [None] * capacity
for i in range(size):
bigger[i] = table[i]
copies = copies + 1
table = bigger
table[size] = item
size = size + 1
return size + copies

Invariant: After every insert, the total number of copies is less than twice the number of items, so the total cost is at most 3n.

Start

Local variables

Orange = changed in this step

`items` list

538192746

Call stack

dynamic_table()line 1

Step 1 of 104

How the work grows with input size

Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

insert
copy
current input (n=9)

Show as a table

n	insert	copy
4	4	3
6	6	7
8	8	7
10	10	15
12	12	15
14	14	15
16	16	15

Explanation

The idea

We want an array we can keep inserting into. When the table is full, make one twice as big and copy every item into it.

Amortized analysis

A single insert can be expensive (copying the whole table), but such inserts are rare. After n inserts the copies add up to 1 + 2 + 4 + … < 2n; so the total cost is under 3n, and the amortized cost of an insert is O(1).

The accounting method: pay 3 coins per insert: one for the insert itself, one for this item's future copy, and one for the future copy of an older item. The coins always suffice.

What to watch in the trace

The bars are the current table, empty slots included.
The growth chart shows that the copies grow linearly, not quadratically.