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.

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}ⁿ}{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²) steps to sort them; therefore the worst-case time-complexity of insertion sort is of O(n²).

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