Data Structures & Algorithms / Optimization proofs and maintained aggregates / Lesson 18

Amortized costs and algorithm selection

Bound operation sequences without confusing amortization, randomness, worst-case latency, or measured implementation behavior.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

One expensive operation can fit a cheap total sequence
Model doubling explicitly instead of guessing Python capacity
Charge each queue element for one transfer

One expensive operation can fit a cheap total sequence

Amortized analysis bounds total cost across a sequence of operations, including occasional expensive ones. It does not average over random input unless randomness is separately part of the model. A dynamic array that doubles capacity can occasionally copy every stored element, yet the total copied across many appends is geometrically bounded. This does not promise every append has constant worst-case latency. If a real-time task needs a strict per-operation deadline, an amortized guarantee alone may be insufficient. Name the sequence, starting state, charged work, and allowed operations before presenting an average-looking number.

Model doubling explicitly instead of guessing Python capacity

The first program counts writes and copied elements in an abstract doubling array. It is not an inspection of CPython’s actual allocation policy. Starting at capacity zero, the first allocation creates one slot, then later full capacities double. The copies before reaching n entries form1+2+4 and so on, less than2n for positive n. Adding n element writes gives a linear aggregate bound. The example records resize events so the expensive individual steps remain visible. Python’s implementation can choose different growth details while supporting an appropriate amortized append contract.

python Self-contained Python3 algorithm example using synthetic local data.

def doubling_model(n):
    if type(n) is not int or n < 0:
        raise ValueError("Count must be a nonnegative integer")
    size = capacity = cost = 0
    resizes = []
    for _ in range(n):
        if size == capacity:
            new_capacity = max(1, 2 * capacity)
            cost += size
            resizes.append((size, new_capacity))
            capacity = new_capacity
        size += 1
        cost += 1
    return cost, resizes

print(doubling_model(8))
print(doubling_model(0))

Expected output

(15, [(0, 1), (1, 2), (2, 4), (4, 8)])
(0, [])

Eight writes plus seven copied elements cost15 in this model. No runtime allocation size or benchmark timing is measured.

Charge each queue element for one transfer

The second program implements FIFO using an incoming stack and an outgoing stack. New items enter incoming. When outgoing is empty, transferring all incoming items reverses their order so the oldest reaches the outgoing top. Each element crosses from incoming to outgoing at most once before removal. Across n pushes and at most n successful pops, transfers are at most n, even though one pop can transfer many elements. This aggregate proof assumes the underlying stack operations have their stated costs; with dynamic-array stacks, their own amortized bounds must also be included consistently.

python Self-contained Python3 algorithm example using synthetic local data.

class TwoStackQueue:
    def __init__(self):
        self.incoming, self.outgoing = [], []
        self.moves = 0
    def push(self, value):
        self.incoming.append(value)
    def pop(self):
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())
                self.moves += 1
        if not self.outgoing:
            raise IndexError("Queue is empty")
        return self.outgoing.pop()

queue = TwoStackQueue()
queue.push("A")
queue.push("B")
first = queue.pop()
queue.push("C")
second, third = queue.pop(), queue.pop()
print(first, second, third)
print(queue.moves)

Expected output

A B C
3

C waits while B is already in outgoing. Each of A,B,C transfers once and preserves FIFO order.

Potential and accounting explain the same conserved work

An accounting proof can charge extra credit to each push and spend that credit when its item transfers. A potential function can instead measure stored future work, such as a multiple of incoming-stack size. The amortized cost is actual cost plus potential change. The potential should remain bounded below under the chosen starting state so total actual work is controlled. Do not invent negative credit that makes every operation appear free without paying initial or terminal obligations. The goal is a valid sequence inequality, not a cosmetic assignment of smaller numbers to expensive operations.

Select algorithms from constraints and required outputs

A comparison-based full sort has different lower-bound assumptions from integer counting or radix methods. Producing every matching pair can require quadratic output even when finding one pair is linear under hashing assumptions. A streaming top-k query differs from sorting all input, and static range queries differ from online updates. Write the output and operation mix before comparing asymptotic labels. Include memory, preprocessing, key cost, numeric representation, worst-case requirements, and failure policy. A theoretically attractive bound does not excuse an invalid precondition or a result contract weaker than the user’s task.

Use deterministic counters and independent references

For the doubling model, check total cost grows within the proved linear envelope over small n and inspect resize boundaries separately. For the queue, compare finite mixed push/pop sequences with collections.deque and verify no item transfers twice. Record operation counts separately from wall-clock time; tiny timing results may mostly reflect interpreter overhead. The course’s isolated Python execution and finite differential checks establish exact outputs and tested properties, not a production latency benchmark or a proof over every possible input. Keep those limits visible when reporting algorithm improvements.

Common errors and fixes

Amortized constant cost is promised as constant latency

Why it happens: A total-sequence bound was applied to every individual operation.
How to fix it: State both the occasional worst case and the aggregate bound.
Prevent it next time: Inspect resize and transfer-triggering operations.

A doubling model is reported as CPython measurement

Why it happens: Abstract counted work was confused with implementation observation.
How to fix it: Label the modeled policy and measure implementations separately if needed.
Prevent it next time: Attach model assumptions to every cost result.

Only input size is counted for a huge output

Why it happens: The result contract’s output lower bound was omitted.
How to fix it: Include output-sensitive work and space in analysis.
Prevent it next time: Contrast find-one with enumerate-all tasks.

Check your understanding

1. Why can one queue pop be linear while a whole sequence remains linear?

Show worked solution

That pop may transfer all waiting incoming items. Each transferred item then stays in outgoing until removed and is never transferred again. Summing across the sequence charges each item once, so occasional bursts do not multiply into quadratic total work.

2. Does expected hashing performance mean the same as amortized resizing?