Amortized Analysis: Aggregate, Banker's & Physicist's Potential (Φ)

Three Frameworks: Aggregate, Accounting (Banker's) & Potential ($\Phi$)

Let a sequence of $m$ operations act on a data structure starting at state $D_0$, transitioning through states $D_1, D_2, \dots, D_m$ with actual operation costs $c_1, c_2, \dots, c_m$. All three amortized frameworks upper-bound the total actual cost $\sum_{i=1}^m c_i$:

• 1. Aggregate Method: Bound the entire sequence cost $T(m) = \sum_{i=1}^m c_i$ directly (e.g., via geometric series or bit-flip frequency), then assign every operation the uniform amortized cost $T(m)/m$.
• 2. Accounting (Banker's) Method: Charge each operation $i$ an amortized fee $\hat{c}_i$. When $\hat{c}_i > c_i$, store the surplus $\hat{c}_i - c_i$ as prepaid credit attached to specific elements in the data structure. When an expensive operation occurs ($c_i > \hat{c}_i$), spend the stored credits to pay the difference. As long as total credit never goes negative ($\sum_{i=1}^k \hat{c}_i \ge \sum_{i=1}^k c_i$ for all $k$), $\sum \hat{c}_i$ upper-bounds total actual work.
• 3. Physicist's Potential Method ($\Phi$): Define a global state function $\Phi: \mathcal{D} \to \mathbb{R}$ mapping each data structure state $D_i$ to a scalar "stored potential energy". Define the amortized cost of operation $i$ as: $$\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) = c_i + \Delta \Phi_i$$

Visualizing Dynamic Array Potential Sawtooth $\Phi(n, m) = 2n - m$

Notice how $\Phi(n, m) = 2n - m$ climbs by $+2$ on every normal insertion, peaks at $\Phi = m$ when the buffer is full ($n = m$), and immediately drops back to $\Phi = 2$ upon doubling capacity to $2m$—releasing the exact stored energy needed to copy all $n$ elements.

Production Implementation: De-Amortized vs Amortized Two-Stack Queue

The C++20 implementation below shows the classic Two-Stack FIFO Queue alongside an explicit potential verifier that asserts $\hat{c}_i = c_i + \Delta \Phi_i \le 3$ on every single operation.

// C++20: Two-Stack FIFO Queue with Runtime Potential Verification (Phi = 2 * inStack.size())
#include <cassert>
#include <cstddef>
#include <vector>

template <typename T>
class AmortizedTwoStackQueue {
    std::vector<T> inStack_;
    std::vector<T> outStack_;

public:
    // Potential function Phi(D) = 2 * |inStack| >= 0
    size_t potential() const noexcept { return 2 * inStack_.size(); }

    // Actual cost c_i = 1, Delta Phi = +2 ==> Amortized cost c_hat = 3
    void enqueue(T value) {
        const size_t phiBefore = potential();
        inStack_.push_back(std::move(value));
        const size_t actualCost = 1;
        const ptrdiff_t amortizedCost = static_cast<ptrdiff_t>(actualCost + potential())
                                      - static_cast<ptrdiff_t>(phiBefore);
        assert(amortizedCost == 3);
    }

    // If outStack is empty, pours k = |inStack| items:
    // Actual cost c_i = 2k + 1, Delta Phi = -2k ==> Amortized cost c_hat = 1!
    T dequeue() {
        const size_t phiBefore = potential();
        size_t actualCost = 0;

        if (outStack_.empty()) {
            while (!inStack_.empty()) {
                outStack_.push_back(std::move(inStack_.back()));
                inStack_.pop_back();
                actualCost += 2; // 1 pop + 1 push
            }
        }
        T front = std::move(outStack_.back());
        outStack_.pop_back();
        actualCost += 1;

        const ptrdiff_t amortizedCost = static_cast<ptrdiff_t>(actualCost + potential())
                                      - static_cast<ptrdiff_t>(phiBefore);
        assert(amortizedCost == 1);
        return front;
    }
};