Worst-case time complexity

Worst-case time complexity denotes the longest running time W(n) of an algorithm given any input of size n. It gives an upper bound on time requirements and is often easy to compute. The drawback is that it can be overly pessimistic.

Example

Algorithm contains(x, arr):
   for i = 0 to len(arr)-1
       if x == arr[i]
            return true
   return false

The number of comparisons this algorithm performs depends not only on the number of elements, n, in the array but also on the value of x and the values in arr:

• If x isn't found in arr the algorithm makes n comparisons,
• but if x equals arr[0] there is only one comparison.

The worst-cast time complexity thus becomes W(n) = n. We often use asymptotic notation and write W(n) ∊ Θ(n), and say that this is a linear time algorithm.