Worst case complexity
Encyclopedia
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.
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 TA:N→N, defined by TA(n):= maxx∈{0, 1}n{tA(x)}.
Similar definitions can be given for space complexity, randomness complexity, etc.
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(n2) steps to sort them; therefore the worst-case time-complexity of insertion sort is of O(n2).
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, 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
Average-case complexity
Average-case complexity is a subfield of computational complexity theory that studies the complexity of algorithms on random inputs.The study of average-case complexity has applications in the theory of cryptography....
, which is an average measure of the amount of resources the algorithm uses on a random input.
Definition
- Given a model of computationModel of computationIn computability theory and computational complexity theory, a model of computation is the definition of the set of allowable operations used in computation and their respective costs...
and an algorithm A that halts on each input x, the mapping tA:{0, 1}*→N is called the time complexity of A if, for every x, A halts after exactly tA(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 TA:N→N, defined by TA(n):= maxx∈{0, 1}n{tA(x)}.
Similar definitions can be given for space complexity, randomness complexity, etc.
Examples
Consider performing insertion sortInsertion sort
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
on n numbers on a random access machine
Random access machine
In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...
. 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(n2) steps to sort them; therefore the worst-case time-complexity of insertion sort is of O(n2).