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 12 August 2019.
HTML page formatted Mon Aug 12 09:59:40 2019.

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