Worst-case complexity

In computer science, worst case complexity is a performance measure of an algorithm. It is defined as the maximum of the complexity measure of the algorithm over all possible input instances of the same size.

The complexity measure most commonly used is the running time of the algorithm, although other measures may also be used (the amount of memory used, the number of packets sent over a network, etc.). The size measure most commonly used is the number of bits comprising the input instance, although, again, other measures may be used (the number of vertices in a graph, etc.).

Formally the worst case complexity is:

Worst Case Complexity w = {sup(S) | S = \-/ f s.t there exist a c,B > 0 s.t \-/ n >= B g(n) = c * f(n) } where g(n) is your algorithm. In plain english this means that the worst case complexity is the smallest element in the set of all functions such that g is in O(f(n)) for all n greater then B,which is the breaking point.

Finding the worst case complexity involves looking at the most number of steps any piece of code will perform. Here is an example using linear search on an Array A, in java.

   public int search(A,x){
     boolean found = false;
     int c = 0;
     int index = -1;
     while ((c < A.size()) && (found == false)){
       if A[c] = x {
         found = true;
         index = c;
       }
     }return index;
   }

In this case clearly the worst case is O(n). This is because at worst the loop has to run all the way through the array once to find the object(or not find it). This would mean that the algorithm would have to make n comparisons and runs in n time. The requirements for this worst case complexity are the element is not in the array, or the element is the last element in the array. Cleary there is no input which would make the algorithm run in worse then O(n) time as the loops will only ever run from 0 - n-1 = n.

References

On the theory of average case complexity, Proceedings of the twenty-first annual ACM symposium on Theory of computing, 1989

Katoen,Joost-Pieter Introduction to Algorithm Analysis Lecture Notes,2002.

Worst-case complexity

See also

References

Further readings