Worst-case complexity

(Redirected from 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

edit

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

edit

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:

 

Quite frequently, the wording is:

  • „Algorithm   has the worst-case complexity  .“

or even only:

  • „Algorithm   has complexity  .“

Examples

edit

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

edit

References

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