In computer science (specifically computational complexity theory), the worst-case complexity measures the resources (e.g. running time, memory) that an algorithm requires given an input of arbitrary size (commonly denoted as in asymptotic notation). It gives an upper bound on the resources required by the algorithm.

In the case of running time, the worst-case time complexity indicates the longest running time performed by an algorithm given any input of size , and thus guarantees that the algorithm will finish in the indicated period of time. The order of growth (e.g. linear, logarithmic) of the worst-case complexity is commonly used to compare the efficiency of two algorithms.

The worst-case complexity of an algorithm should be contrasted with its average-case complexity, which is an average measure of the amount of resources the algorithm uses on a random input.

Definition

Given a model of computation is called the time complexity if, for every input string steps.

Since we usually are interested in the dependence of the time complexity, defined by the maximal complexity

.

Similar definitions can be given for space complexity, randomness complexity, etc.

Ways of speaking

is given in asymptotic Big-O Notation and the meaning:

• There exists a positive real number and a natural number such that

Quite frequently, the wording is:

• .“

or even only:

• .“

Examples

Consider performing insertion sort numbers on a random-access machine.

See also

• Analysis of algorithms

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Chapter 2.2: Analyzing algorithms, pp.25-27.

• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. , p.32.