Best, Average and Worst Case

One algorithm, different inputs

The amount of work performed by the same algorithm can depend not only on the input size, but also on the data itself. For example, a linear search can find the target immediately, in the middle of the array, or fail to find it at all.

int index = -1;

for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] == target) {
        index = i;
        break;
    }
}

If target is in the first cell, only one check is performed. If it is absent or located at the very end, the entire array must be examined. So inputs of the same size can require different amounts of work.

Best and worst case

The best case describes the most favorable input of a given size. For the search above, this happens when the element is found immediately: O(1).

The worst case describes the maximum amount of work among inputs of the same size. For linear search, up to n elements must be checked, so the worst case is O(n). This estimate is especially useful when a clear upper bound on the cost is needed.

Average case requires a model

The average case tries to describe the typical cost across many possible inputs. But the word “average” is not enough by itself: you need to know which inputs are possible and how likely they are. Without such a model, an average estimate can become little more than an assumption.

For linear search, under the natural assumption that the target is equally likely to appear at any position, a fraction of the array is examined on average. The constant factor is dropped, so the asymptotic estimate remains O(n).

Always name the case you are analyzing

The statement “the algorithm runs in O(n)” can be insufficiently precise when its behavior depends strongly on the input. In casual discussion, the worst case is sometimes assumed by default, but it is better to state the context explicitly, especially when the best, average, and worst cases differ.