Chapter notes

Aggregate analysis was used by Aho, Hopcroft, and Ullman [5]. Tarjan [293] surveys the accounting and potential methods of amortized analysis and presents several applications. He attributes the accounting method to several authors, including M. R. Brown, R. E. Tarjan, S. Huddleston, and K. Mehlhorn. He attributes the potential method to D. D. Sleator. The term "amortized" is due to D. D. Sleator and R. E. Tarjan.

Potential functions are also useful for proving lower bounds for certain types of problems. For each configuration of the problem, we define a potential function that maps the configuration to a real number. Then we determine the potential Φ_init of the initial configuration, the potential Φ_final of the final configuration, and the maximum change in potential ΔΦ_max due to any step. The number of steps must therefore be at least |Φ_final - Φ_init|/|ΔΦ_max|. Examples of the use of potential functions for proving lower bounds in I/O complexity appear in works by Cormen [71], Floyd [91], and Aggarwal and Vitter [4]. Krumme, Cybenko, and Venkataraman [194] applied potential functions to prove lower bounds on gossiping: communicating a unique item from each vertex in a graph to every other vertex.