14.3 Supplement: Amortized Analysis

Prerequisites: Asymptotic Analysis. This section demonstrates the aggregate, accounting, and potential methods using a dynamically resized array that doubles in capacity. It then contrasts amortized bounds with average-case behavior using a binary counter.

Why a Single Append Operation Can Be Slow

When a dynamic array has available slots, appending simply writes to one position. However, when the array is full, it must allocate larger storage, copy all existing elements, and then write the new value. The worst-case cost for a single append is Θ(n), but n consecutive appends starting from an empty array still have total cost Θ(n).

Amortized analysis provides guarantees for a sequence of operations without assuming any specific probability distribution of inputs. It does not claim that every individual operation is fast; systems with strict tail latency requirements must still account for expansion pauses, or adopt strategies such as pre-allocating capacity, segmented storage, or incremental migration.

Record the Actual Cost

Count an ordinary write as 1 unit and each copied old element as 1 unit. This analytical counter omits Python’s [None] initialization, old-list release, and trace recording; it does not measure elapsed time. Including these linear initialization costs preserves the geometric-growth asymptotic bound but changes its constants.

class DynamicArray:
    def __init__(self):
        self._data = [None]
        self._size = 0
        self._actual_costs = []

    def append(self, value):
        actual = 1
        if self._size == len(self._data):
            old = self._data
            self._data = [None] * (2 * len(old))
            for index, item in enumerate(old):
                self._data[index] = item
                actual += 1

        self._data[self._size] = value
        self._size += 1
        self._actual_costs.append(actual)

    @property
    def capacity(self):
        return len(self._data)

    def to_list(self):
        return self._data[:self._size]

    def actual_costs(self):
        return self._actual_costs.copy()

array = DynamicArray()
for number in range(16):
    array.append(number)

assert array.to_list() == list(range(16))
assert array.capacity == 16
assert array.actual_costs() == [1, 2, 3, 1, 5, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 1]
assert sum(array.actual_costs()) == 31

The expansion cost appears on the 2nd, 3rd, 5th, and 9th append operations, because the old capacity is sequentially 1, 2, 4, 8. The expensive steps still exist, though they occur less frequently, spaced out by a geometric progression.

Aggregate Analysis: Calculate the Total

n writes individually cost n. When capacity doubles, the total replication cost becomes:

copies = 1 + 2 + ... + C/2 = C - 1 < 2n
actual total = n + C - 1 < 3n  (n > 0, C = final capacity)

For n>0, final capacity C satisfies n <= C < 2n, so every prefix costs less than 3n and appends cost O(1) amortized. Only when n is a power of two do we have C=n and total cost 2n-1. At n=9, for example, 15 copies plus 9 writes cost 24, already exceeding 2n. No random-append assumption is needed.

If capacity grows by adding 1 instead of multiplying by 2 the replication cost becomes 1+2+...+(n-1), and the total cost is Θ(n²). The geometric growth factor is essential to establishing this conclusion.

Accounting Method: Cheap Operations Build Credit for the Future

Charge each append 3 units in the analysis:

• 1 unit is used for the current write;
• the remaining credit is preserved to fund future copies of old elements.

We simply verify that the credit after every operation is never negative.

def accounting_costs(operation_count):
    if not isinstance(operation_count, int) or operation_count < 0:
        raise ValueError("operation_count must be a non-negative integer")
    capacity = 1
    size = 0
    credit = 0
    trace = []

    for _ in range(operation_count):
        actual = 1
        if size == capacity:
            actual += capacity
            capacity *= 2
        size += 1
        credit += 3 - actual
        if credit < 0:
            raise AssertionError("credit became negative")
        trace.append((actual, credit))

    return trace

trace = accounting_costs(1_000)
assert all(actual <= 3 + previous_credit
           for (actual, _), previous_credit
           in zip(trace, [0] + [credit for _, credit in trace[:-1]]))

Other charges are possible if the resulting credit never becomes negative under the same actual-cost model. Credit is an analytical tool, not a field the program needs to maintain. Cornell’s amortized-analysis lecture also compares these methods using dynamic arrays.

Potential Method: Expressing Credit as a State Function

Potential can be defined as:

Phi = 0                         size = 0
Phi = 2 * size - capacity       size > 0

When the capacity doubles and no shrinking occurs, a non-empty array always satisfies capacity/2 < size <= capacity, ensuring that potential remains non-negative. The amortized cost is defined as:

amortized = actual + Phi_after - Phi_before

def potential_costs(operation_count):
    if not isinstance(operation_count, int) or operation_count < 0:
        raise ValueError("operation_count must be a non-negative integer")
    capacity = 1
    size = 0
    potential = 0
    amortized_costs = []

    for _ in range(operation_count):
        before = potential
        actual = 1
        if size == capacity:
            actual += capacity
            capacity *= 2
        size += 1
        potential = 2 * size - capacity
        amortized_costs.append(actual + potential - before)

    return amortized_costs

costs = potential_costs(1_000)
assert costs[0] == 2
assert all(cost <= 3 for cost in costs)

The first amortized cost for an append operation is 2, and all subsequent ones are at most 3. Applying 2*size-capacity to the empty array would give initial potential -1, not the 0 defined here. Mixing those initial conventions miscalculates the first step. Potential must be consistently defined across all states.

When summing amortized costs, intermediate potentials cancel out:

sum(amortized) = sum(actual) + Phi_final - Phi_initial

Since both initial and final potential values are non-negative and the initial potential is zero, the actual total cost never exceeds the sum of amortized costs.

Binary Counter: A Bit May Flip Repeatedly

Start from 0 and increment. Each operation might clear a trailing sequence of 1s and flip the next 0 to 1, with a worst-case cost of Θ(log n) per step. However, the least significant bit flips once per increment, the next bit flips every two steps, and higher bits flip with ever-decreasing frequency, halving each time.

def count_bit_flips(increments):
    if not isinstance(increments, int) or increments < 0:
        raise ValueError("increments must be a non-negative integer")

    value = 0
    total = 0
    for _ in range(increments):
        probe = value
        flips = 1
        while probe & 1:
            flips += 1
            probe >>= 1
        total += flips
        value += 1
    return total

for n in (1, 2, 4, 8, 16, 64):
    assert count_bit_flips(n) == 2 * n - 1

For n>0, total flips equal n + floor(n/2) + floor(n/4) + ... = 2n - popcount(n) < 2n, where popcount(n) counts the 1 bits of n. The example uses powers of two, each with one set bit, so every result is 2n-1; n=0 gives 0. Counting each flip as one unit yields O(1) amortized cost. The Python function simulates this count with integer shifts; it does not claim arbitrary-size integer shifts and additions are constant-time. This remains a deterministic analysis of the operation sequence, not an average over randomly chosen values.

How to Choose Among the Three Methods

Method	Suitable Entry Point	What It Proves
Aggregate	Total cost can be directly summed	An upper bound on the total cost of any n operations
Accounting	Clearly shows which operations save credit for future work	All prefix credits remain non-negative
Potential	Multiple operations share a complex state	The potential function is well-defined, non-negative, and its amortized cost covers the actual cost

The inverse Ackermann bound for union-find and the logarithmic amortized bound for splay trees require a more refined potential function. The proof of the dynamic array in this section cannot be directly transferred; each data structure must select its analysis metric based on how its state evolves.

Hands-on: Calculate a Sequence of Operations

1. Manually compute the actual cost, amortized credit, and potential for the first nine append operations on a dynamic array.
2. Change the growth factor to 1.5 and discuss how rounding affects the upper bound of the geometric growth sequence.
3. How can dynamic arrays avoid oscillating capacity near boundaries when shrinking during low utilization?
4. The stack supports push and multipop(k). Starting from an empty stack, use its element count as potential to prove O(n) total cost for n operations. How does the bound change with s initial elements?
5. Explain why "amortized O(1)" cannot serve as a guarantee for an individual-operation latency SLA.

Account for the Full Cost

Amortized analysis doesn't erase the cost of expansion and replication. It sums up the true cost of all operations and demonstrates that expensive steps occur infrequently enough. Aggregate, accounting, and potential are just three ways of tracking cost; the prerequisites, state functions, and operation sequences must be clearly defined.

Next, explore Advanced Data Structures, where union-find with path compression serves as another example of a "single step not obvious, but bounded when viewed in sequence."