Amortised, expected and measured cost

Amortised analysis distributes total sequence cost across operations without requiring probability. A doubling dynamic array occasionally copies n elements, but all copies over n appends sum geometrically to O(n). A single append is worst-case O(n) and amortised O(1).

Aggregate analysis counts the total; accounting assigns credits; the potential method uses stored work Φ. Expected analysis instead specifies a probability distribution. Random-pivot quicksort expectations concern algorithmic randomness, not an unsupported assumption about typical users.

Benchmarks should record distributions, warm-up, repetitions, median/p95, memory and environment. Cache effects and constants matter within the same asymptotic class. Amortised O(1) does not guarantee low latency for every service request; resizing spikes can matter.

Where potential accumulates in a dynamic array

When a full array doubles capacity, copied old elements form 1+2+4+… . The last term is smaller than n and their sum is below 2n. Together with n writes for new elements, n appends take linear work. One append can still cost Θ(n); amortised cost per append is Θ(1). This is not an average over random inputs.

Accounting charges a few credits per append: one for the current write and others toward future resizing. Potential analysis formalises this as Φ(state). Amortised cost equals actual cost plus ΔΦ. Initial potential must be controlled and potential must stay bounded below over the sequence.

Shrinking needs hysteresis. Resizing at half-full in both directions can let alternating insert/delete operations thrash. Growing when full and shrinking at quarter-full allows cheap operations to accumulate between resizes. Amortised guarantees do not bound the latency of an individual request.

Foundation: Trace resizing across eight appends. Intermediate: Derive the geometric copying bound for a 1.5 growth factor. Advanced: Design incremental migration for tighter per-operation latency, stating lookup invariants while two buffers coexist.

def copied_items(n):
    capacity, size, copied = 1, 0, 0
    for _ in range(n):
        if size == capacity:
            copied += size
            capacity *= 2
        size += 1
    return copied
assert copied_items(16) == 15