# 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

Algorithmcontains(x, arr):fori = 0tolen(arr)-1ifx == arr[i]returntruereturnfalse

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

## Comments