Chapter notes

| < Day Day Up > |

## 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.

| < Day Day Up > |