# Worst-case complexity

In computer science, the **worst-case complexity** (usually denoted in asymptotic notation) measures the resources (e.g. running time, memory) an algorithm requires in the worst-case. 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 *n*, and thus this guarantees that the algorithm finishes on time. Moreover, the order of growth of the worst-case complexity is 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.

## Contents

## Definition

- Given a model of computation and an algorithm
**A**that halts on each input*x*, the mapping*t*_{A}:{0, 1}*→**N**is called the**time complexity**of**A**if, for every*x*,**A**halts after exactly*t*_{A}(*x*) steps.

Since we usually are interested in the dependence of the **time complexity** on different input length, abusing terminology, the time complexity is sometimes referred to the mapping T_{A}:**N**→**N**, defined by T_{A}(*n*):= max_{x∈{0, 1}n}{t_{A}(x)}.

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

## Examples

Consider performing insertion sort on *n* numbers on a random access machine. The best-case for the algorithm is when the numbers are already sorted, which takes O(*n*) steps to perform the task. However, the input in the worst-case for the algorithm is when the numbers are reverse sorted and it takes O(*n ^{2}*) steps to sort them; therefore the worst-case time-complexity of insertion sort is of O(

*n*).

^{2}## See also

## References

- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 2.2: Analyzing algorithms, pp.25-27.
- Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. ISBN 0-521-88473-X, p.32.