§ Amortized complexity from the verifier perspective

• If we want an API that can verify amortized complexity, then each method returns two costs: (a) "number of cycles" spent on the operation, (b) "claimed cost" of the operation. For example, vector.push_back() may return "number of cycles" to be as large as O(n) when doubling, while always returning "claimed cost" as 1.
• At the end of any sequence of operations, the verifier verifies that sum (claimed cost) > sum of (#cycles).
• This establishes that the claimed/amortized cost is an upper bound on the real cost!