# 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

Be the first to comment!