Worst Case Analysis


We've been using a worst case analysis so far. Why?

Back to a linear search of a list of size "n". In the worst case we'll scan the entire list -- performance O(n).

Why be so pessimistic?


However, there are cases where we would want to use different analysis types.

Average-Case


We know that the worst-case assumption protects us from being overly optimistic. But at times, it will be overly pessimistic.

We might consider an "average-case" approach. The "average-case" analysis is pretty rare for a couple reasons:

1. Input Data Assumptions Limit the Algorithm
It makes assumptions about the input data. This means that we would limit our algorithm to a certain input pattern (e.g., random input). Most algorithms do not limit input patterns.
2. Assumptions About Input are Difficult
Think about a simple linear search (scan):
  • Worst-case says we scan n elements
  • We might think average-case would say we scan (1/2)n elements
  • However we have ignored failed searches (which would scan all elements). How many searches result in no match. This may not be easy to estimate.

We'll next look a more common technique called "amortized analysis".

Amortized Analysis


An amortized analysis is especially useful when an algorithm has a worst-case cost only on rare occasions.

Consider the algorithm for "append/add" operation for a dynamic array (resizable array) structure:


Performance of steps:


A worst-case analysis would give this algorithm a big-O level of O(n).

However, we know that the slower "grow" operation is rare. An amortized analysis effectively ignores the rare step thus giving this algorithm a big-O level of O(1)

For a mathematical look at this analysis, baeldung.com does a nice job....

Unlike the average-case approach, this technique does not depend on the input data. It estimates cost over a sequence of operations.

Upper Bound


We might hear the word "upper and lower bounds" in discussions of algorithm performance.

Big-O generally describes an upper bound (asymptotic upper bound).

The use of bounds is a large topic by itself that we will not cover here. If interested, for fun, here is more information...