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.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s