NIST

average-case cost

(definition)

Definition: The sum of costs of an algorithm over all possible inputs divided by the number of possible inputs.

See also worst-case cost, amortized cost, average case, best-case cost.

Note: From Algorithms and Theory of Computation Handbook, page 1-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

More information

Average Case Complexity Forum


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 September 2008.
HTML page formatted Fri Feb 23 10:06:07 2018.

Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "average-case cost", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2008. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/averageCaseCost.html