(definition)
Definition: A measure of a data structure whose change after an operation corresponds to the time cost of the operation.
See also amortized cost.
Note: If an inexpensive operation results in an increase of the potential function, but the increase of the potential function is within a constant factor of the actual cost of the operation, the amortized cost of the operation is unchanged. Meanwhile, if an expensive operation results in a decrease of the potential function that offsets the cost of the expensive operation, the amortized cost of the expensive operation may be small. For such an analysis to remain valid, the potential function must stay nonnegative, and begin with a value of zero. For more on amortized analysis and its origins see Tarjan.
Author: CLK
R. E. Tarjan, Amortized computational complexity, SIAM Journal on Algebraic and Discrete Methods, 6(2):306-318, 1985.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Fri Dec 17 12:06:41 2004.
HTML page formatted Wed Oct 26 09:47:58 2005.
Cite this as:
Chris L. Kuszmaul, "potential function", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/potentialfnc.html
