Since @jamey brought it up, here's the introductory amortization problem: You have a binary number implemented as an arbitrarily long array of booleans. 5, for example, is [true, false, true]. Prove that increment runs in O(1) amortized time.