Aggregate Method for Amortized Analysis, in depth: total-cost bounds, multipop and monotonic stacks, pointer arguments, graph traversals and where it breaks

Bound the total, then divide

Formally, if every sequence of n operations from the initial state costs at most T(n), the amortized cost per operation is T(n)/n, and that figure applies to every operation type equally. Worst-case analysis bounds each operation separately and multiplies, which overestimates when the expensive case cannot repeat back to back. Amortized cost is not an average over random inputs: it is a worst-case guarantee over sequences. No probability is involved, and no input distribution is assumed.

The recipe has four steps. Identify the work that varies (pops, pointer moves, element copies). Find something finite that the work consumes: items pushed, positions in the input, edges in a graph. Prove each unit of that resource is consumed a bounded number of times. Add the fixed per-operation cost and divide by n.

The multipop stack

Take a stack with three operations: PUSH(x), POP and MULTIPOP(k), which pops min(k, size) items. A single MULTIPOP can cost up to n, so a naive worst-case bound for n operations is O(n²). The aggregate argument is one line: an item can be popped at most once for each time it was pushed. Starting from an empty stack, total pops across POP and MULTIPOP are at most the number of PUSHes, which is at most n. Total cost is therefore at most 2n, and each operation is O(1) amortized.

class Stack:
    def __init__(self):
        self.items, self.cost = [], 0

    def push(self, x):
        self.items.append(x)
        self.cost += 1

    def pop(self):
        if self.items:
            self.items.pop()
            self.cost += 1

    def multipop(self, k):
        while k > 0 and self.items:
            self.items.pop()
            self.cost += 1
            k -= 1

Note the phrase starting from an empty stack. If the stack already holds m items, the bound becomes 2n + m. That seems pedantic until a cache warmed from disk or a structure restored from a snapshot breaks a claimed O(n).

Monotonic stacks: pushed once, popped at most once

The same argument powers the monotonic stack, used for next greater element, stock span, largest rectangle in a histogram and many sliding-window problems. Each index is pushed exactly once and popped at most once, so the nested while loop does at most n pops in total even though one iteration can pop many.

def next_greater(xs):
    out = [-1] * len(xs)
    stack = []                     # indices whose answer is still unknown
    ops = 0
    for i, x in enumerate(xs):
        while stack and xs[stack[-1]] < x:
            out[stack.pop()] = x    # every pop is charged to the popped index
            ops += 1
        stack.append(i)
        ops += 1
    return out, ops                 # ops <= 2 * len(xs) for every input

The sliding window minimum uses a monotonic deque and is analysed identically: each index enters the deque once and leaves it at most once, from either end. The bound does not depend on the window size or on the input order.

Worked example: tracing next greater element

Trace next_greater([2, 7, 3, 1, 5, 4, 8, 6]). The stack holds values here for readability; the code stores their indices.

Total: 8 pushes and 6 pops, 14 stack operations against the aggregate bound of 2n = 16. The two values left on the stack, 8 and 6, have no greater element to their right and keep the default of -1. The step for x = 8 alone did four operations, which a per-step worst-case bound would have multiplied by eight. Comparisons follow the same accounting: each successful comparison precedes a pop, and each step has at most one failing comparison that ends its loop, so comparisons are at most 2n as well; this trace makes 11.

Pointer arguments: two pointers and KMP

A second family charges work to positions instead of items. In a two-pointer scan where both indices only move forward through an array of length n, the inner loop can run many times in one outer iteration, but each pointer moves at most n times in total, so the whole scan is O(n).

The KMP prefix function is the classic subtler case. Let k be the length of the current matched border. The outer loop raises k by at most one per position, so total increases are at most n - 1. Every iteration of the inner fallback loop lowers k by at least one, and k never goes below zero. Total decreases therefore cannot exceed total increases, so the inner loop runs at most n - 1 times across the whole computation.

def prefix_function(s):
    pi = [0] * len(s)
    k = 0
    for i in range(1, len(s)):
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]          # strictly decreases k: at most (total increases) times
        if s[i] == s[k]:
            k += 1                 # at most one increase per i
        pi[i] = k
    return pi

This is an aggregate argument over a quantity rather than over items: something bounded below that only goes up slowly can only come down a bounded number of times in total. Recognising that shape is most of the skill.

Graph traversals and the textbook cases

Graph traversals are aggregate analyses most programmers already use without the name. In breadth-first search a vertex is marked when enqueued, so it is enqueued and dequeued at most once, and its adjacency list is scanned once, at dequeue. A single dequeue may scan V - 1 neighbours, but the scans sum to the total length of all adjacency lists, which is E for a directed graph and 2E for an undirected one. Total work is O(V + E). The same argument fails if you mark vertices at dequeue instead of enqueue: a vertex can then sit in the queue many times, and the per-vertex charge is no longer bounded.

The two textbook examples belong here only briefly, because the potential method article works them in detail. Bit i of a binary counter flips once every 2ⁱ increments, so n increments flip at most n(1 + 1/2 + 1/4 + ...) < 2n bits. A dynamic array that doubles copies 1 + 2 + 4 + ... elements up to its final size, a geometric sum under 2n, so n appends cost under 3n. Grow by a constant amount instead and the copies sum to roughly n²/(2c): the aggregate method shows the difference in one line.

Testing an aggregate bound in code

An aggregate bound is a claim about every sequence, so test it on many sequences, including adversarial ones. Instrument the cost, run random and crafted inputs, and assert the total against the bound for every prefix, not just the final n.

import random

def check_multipop(trials=2000, n=500):
    for _ in range(trials):
        s = Stack()
        for step in range(1, n + 1):
            r = random.random()
            if r < 0.6:
                s.push(step)
            elif r < 0.8:
                s.pop()
            else:
                s.multipop(random.randint(1, 50))
            assert s.cost <= 2 * step, (step, s.cost)

def check_next_greater():
    cases = [list(range(1000)), list(range(1000, 0, -1)),
             [random.randint(0, 9) for _ in range(1000)]]
    for xs in cases:
        _, ops = next_greater(xs)
        assert ops <= 2 * len(xs)

Sorted ascending input is the adversary for the monotonic stack: every element pops its predecessor, giving exactly 2n - 1 operations. Descending input pops nothing. If a test ever exceeds the bound, either the proof assumed something the code does not do, or the code charges work the proof forgot, such as an allocation hidden in a library call.

Where the aggregate method breaks

The method assigns one amortized cost to every operation, which is its main limit. When operations differ in kind, such as cheap inserts and expensive deletes, a single average hides which operations pay. The accounting and potential methods assign different amortized costs per operation type and handle that directly.

The argument also depends on the sequence being free to run only forward. Add DECREMENT to a k-bit binary counter and alternate INCREMENT and DECREMENT at the boundary between 0111...1 and 1000...0: every operation flips all k bits, so n operations cost n times k. Nothing about the counter changed; the set of allowed sequences did. Rollback has the same effect: union-find with undo cannot use path compression, because undo can repeatedly restore the expensive state that compression paid to flatten.

Finally, amortized bounds say nothing about latency. A dynamic array resize that copies ten million elements is O(1) amortized and a visible pause in a request path. When single operations have deadlines, deamortize: resize incrementally, moving a few elements per operation into the new buffer, so worst-case cost per operation is bounded at the price of a larger constant and more complex code.

Aggregate, accounting and potential compared

All three prove the same kind of guarantee. Start with the aggregate method; if the total cannot be bounded without tracking which operation paid, move to the potential method. For the notation underneath all of this, see the Big-O article.

What to do next

1. Write the multipop proof from memory in two sentences, including the empty-start assumption.
2. Implement next_greater with an operation counter and run the ascending, descending and random checks.
3. Prove the KMP prefix function is linear by tracking k, then confirm with an instrumented run on a string like aaaa...ab.
4. Re-derive BFS as O(V + E), then break it deliberately by marking visited at dequeue and measure the queue length.
5. Find one loop in your own code with a nested while that you assumed was quadratic and check whether an aggregate bound applies.
6. For any structure in a latency-sensitive path, measure the worst single operation as well as the average.