§ 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
- 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!