worst-case complexity

{{Short description|Upper bound on resources required by an algorithm}}

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 {{mvar|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 {{mvar|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 $\mathsf{A}$ that halts on each input $s$ , the mapping $t_{\mathsf{A}} \colon \{0, 1\}^\star \to \N$ is called the time complexity of $\mathsf{A}$ if, for every input string $s$ , $\mathsf{A}$ halts after exactly $t_{\mathsf{A}}(s)$ 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 $t_{\mathsf{A}} \colon \N \to \N$ , defined by the maximal complexity

: $t_{\mathsf{A}}(n) := \max_{s\in \{0, 1\}^n} t_{\mathsf{A}}(s)$

of inputs $s$ with length or size $\le n$ .

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

Ways of speaking

Very frequently, the complexity $t_{\mathsf{A}}$ of an algorithm $\mathsf{A}$ is given in asymptotic Big-O Notation, which gives its growth rate in the form $t_{\mathsf{A}} = O(g(n))$ with a certain real valued comparison function $g(n)$ and the meaning:

There exists a positive real number $M$ and a natural number $n_0$ such that

: $|t_{\mathsf{A}}(n)| \le M g(n) \quad \text{ for all } n\ge n_0.$

Quite frequently, the wording is:

„Algorithm $\mathsf{A}$ has the worst-case complexity $O(g(n))$ .“

or even only:

„Algorithm $\mathsf{A}$ has complexity $O(g(n))$ .“

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)$ .

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.

Category:Analysis of algorithms

worst-case complexity

Definition

Ways of speaking

Examples

See also

References