Average-case complexity: Difference between revisions

Revision as of 19:31, 7 May 2021

Revision as of 21:44, 7 May 2021

Line 1:

{{Short description|Computational theory}}

In [[computational complexity theory]], the '''average-case complexity''' of an [[algorithm]] is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with [[worst-case complexity]] which considers the maximal complexity of the algorithm over all possible inputs.