Average-case complexity: Difference between revisions

Revision as of 13:08, 9 November 2021

Revision as of 04:24, 24 February 2022

Line 1:

{{redirect|AvgP|other uses|avgp (disambiguation)}}

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.