A dynamic array that doubles when full copies n items occasionally, but most appends are Θ(1). The amortized cost of append is Θ(1): total work for n appends is Θ(n).

Goal

Simulate doubling growth and print copies versus appends.

Double when full

def grow_appends(n):
    cap = 1
    size = 0
    copies = 0
    for _ in range(n):
        if size == cap:
            copies += cap
            cap *= 2
        size += 1
    return copies, cap

for n in (1, 2, 4, 8, 16):
    copies, cap = grow_appends(n)
    print("n", n, "copies", copies, "cap", cap, "copies/n", copies / n)

Copies stay on the order of n (1+2+4+…+n/2 < n). So copies/n is bounded.

Versus always-copy insert-at-0

def insert_front_cost(n):
    steps = 0
    for size in range(n):
        steps += size
    return steps

for n in (4, 8, 16):
    copies, _ = grow_appends(n)
    print(n, "amortized copies", copies, "insert-front shifts", insert_front_cost(n))

Insert-at-0 is Θ(n²) total. Doubling append is Θ(n) total.

Tip

Python’s list.append uses this idea (over-allocation). You do not manage cap. You do need the word amortized when someone says “append is O(1)”.