scratch
§ Amortized Complexity from the Verifier Perspective
created 2021-08-19
- 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!
❦