Potential-method amortized cost (the defining equation)

Answer

amortized_cost = actual_cost + Phi(D_i) - Phi(D_{i-1}) # Stack with Phi(D) = number of items: # PUSH: 1 + (+1) = 2 # POP: 1 + (-1) = 0 # MULTIPOP: k + (-k) = 0

The amortized cost is actual cost plus the change in potential. Telescoping the sum gives total actual cost + Φ(Dₙ) − Φ(D₀); if Φ never drops below Φ(D₀), the amortized total bounds the real total.