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.