Worst-case complexity

Given a model of computation and an algorithm ${\displaystyle {\mathsf {A}}}$  that halts on each input ${\displaystyle s}$ , the mapping ${\displaystyle t_{\mathsf {A}}\colon \{0,1\}^{\star }\to \mathbb {N} }$  is called the time complexity of ${\displaystyle {\mathsf {A}}}$  if, for every input string ${\displaystyle s}$ , ${\displaystyle {\mathsf {A}}}$  halts after exactly ${\displaystyle 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 ${\displaystyle t_{\mathsf {A}}\colon \mathbb {N} \to \mathbb {N} }$ , defined by the maximal complexity

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

of inputs ${\displaystyle s}$  with length or size ${\displaystyle \leq n}$ .

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

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

• There exists a positive real number ${\displaystyle M}$  and a natural number ${\displaystyle n_{0}}$  such that

${\displaystyle |t_{\mathsf {A}}(n)|\leq Mg(n)\quad {\text{ for all }}n\geq n_{0}.}$ 

Quite frequently, the wording is:

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

or even only:

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

Consider performing insertion sort on ${\displaystyle n}$  numbers on a random-access machine. The best-case for the algorithm is when the numbers are already sorted, which takes ${\displaystyle 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 ${\displaystyle O(n^{2})}$  steps to sort them; therefore the worst-case time-complexity of insertion sort is of ${\displaystyle O(n^{2})}$ .

• Analysis of algorithms

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