## ยง 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!