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.
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
xisn't found in
arrthe algorithm makes n comparisons,
- but if
arrthere 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.