Complexity: Common Classes, Amortized Cost and Space

Amortized analysis: appending to a dynamic array

Python's list, C++'s std::vector and Java's ArrayList allocate a bigger array and copy every element when the current one is full. That one append costs O(n), but if capacity grows by a constant factor, n appends cost O(n) in total, so each costs O(1) amortized.

Doubling the capacity copies 1 + 2 + 4 + ... elements; the last term is smaller than n, so the sum is always below 2n. Growing by a fixed amount instead (say 10 slots) copies 10 + 20 + 30 + ... elements, which adds up to O(n²).

def total_copies(n, grow):
    capacity, size, copies = 1, 0, 0
    for _ in range(n):
        if size == capacity:
            copies += size              # copy existing elements to the new array
            capacity = grow(capacity)
        size += 1
    return copies

for n in (1_000, 10_000, 100_000):
    doubling = total_copies(n, lambda c: c * 2)
    plus_ten = total_copies(n, lambda c: c + 10)
    print(n, doubling, plus_ten)
# 1000 1023 49600
# 10000 16383 4996000
# 100000 131071 499960000

Doubling stays proportional to n (under 2n), while growing by ten multiplies the copies by about 100 when n grows tenfold. Unlike average-case analysis, amortized analysis involves no probability: it is a guarantee over the whole sequence of operations. CPython's list grows by about 1.125x plus a small constant, which still gives amortized O(1). You can watch the allocation change only occasionally:

import sys

items, last = [], sys.getsizeof([])
for i in range(40):
    items.append(i)
    size = sys.getsizeof(items)
    if size != last:
        print(len(items), size)   # only lengths where a reallocation happened
        last = size

Space complexity

Total space includes the input; auxiliary space excludes it. An "in-place" algorithm usually means O(1) or O(log n) auxiliary space. Every recursive call uses a stack frame, so recursion depth is a space cost.

def sum_recursive(items, i=0):      # time O(n), stack space O(n)
    if i == len(items):
        return 0
    return items[i] + sum_recursive(items, i + 1)

def sum_iterative(items):           # time O(n), auxiliary space O(1)
    total = 0
    for x in items:
        total += x
    return total

print(sum_iterative(range(100_000)))   # 4999950000
# sum_recursive(list(range(100_000))) exceeds the default recursion limit (about 1000): RecursionError

Summary

• Differences between classes dwarf constant factors as n grows, and input limits tell you which class you need.
• Dynamic arrays grow by a factor, which makes append amortized O(1); growing by a fixed amount makes it O(n²) overall.
• Space complexity includes auxiliary memory and recursion depth.