# Worst-case complexity Information

*https://en.wikipedia.org/wiki/Worst-case_complexity*

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 n 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 n, 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 and an algorithm that halts on each input , the mapping is called the **time complexity** of if, for every
input string , halts after exactly steps.

Since we usually are interested in the dependence of the **
time complexity** on different input lengths, abusing terminology, the time complexity is sometimes referred to the mapping , defined by the maximal complexity

of inputs with length or size .

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

## Ways of speaking

Very frequently, the complexity of an algorithm is given in asymptotic Big-O Notation, which gives its growth rate in the form with a certain real valued comparison function and the meaning:

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

Quite frequently, the wording is:

- „Algorithm has the worst-case complexity .“

or even only:

- „Algorithm has complexity .“

## Examples

Consider performing insertion sort on numbers on a random access machine. The best-case for the algorithm is when the numbers are already sorted, which takes 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 steps to sort them; therefore the worst-case time-complexity of insertion sort is of .

## 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.