Abstract
Amortization is a principle of data structure design which aims to guarantee an average cost per operation over any sequence of operations, with the high cost of some operations being amortized by the low cost of previous operations. After a reminder of the principles of amortization and amortized-time analysis, the lecture will show examples of persistent data structures that have O(1) complexity provided they are used linearly. We will then study Okasaki's approach to reconciling amortization and general (non-linear) persistence, using lazy (on-demand) evaluation of certain computations.
