# Why would we look at the worst-case running time?

We usually analyze our algorithm by looking at the worst-case running time. But why is that? We have three reasons:

1. The worst-case running time of an algorithm gives us an upper bound on the running time for any input. This provides a guarantee that the algorithm will never take any longer for that particular $n$. We shall not make any educated guess about the running time and hope that it never gets much worse.
2. For some algorithms, the worst case occurs fairly often. For example, in searching a database for a particular piece of information, the searching algorithm’s worst case will often occur, which is when the information is not present in the database.
3. The “average case” is often roughly as bad as the worst case. Suppose that we randomly choose $n$ numbers and apply Insertion-Sort. How long does it take to determine where in sub-array `A[1...j-1]` to insert element `A[j]`? On average, half the elements in `A[1...j-1]` are less than `A[j]`, and half the elements are greater. Therefore, we check half of the sub-array `A[1...j-1]`, and so $t_j$ is about $j/2$. The resulting average-case running time turns out to be a quadratic function $n(n-1)/4$ of the input size $n$, just like the worst-case running time.

Source: Adapted and edited from Introduction to Algorithm, 3rd Ed.