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

- 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 . We shall not make any educated guess about the running time and hope that it never gets much worse.
- 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.
- The “average case” is often roughly as bad as the worst case. Suppose that we randomly choose 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 is about . The resulting average-case running time turns out to be a quadratic function of the input size , just like the worst-case running time.

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

### Like this:

Like Loading...

*Related*