Best Case and Worst Case

We have already seen the best case and the worst case for linear search and binary search. Over all inputs of a given size, the best case is the least work the algorithm does, and the worst case is the most work it does.

Best case analysis means complexity analysis with the best case in mind, and worst case analysis means complexity analysis with the worst case in mind. We can use asymptotic notation to describe either one. Linear search is $O(1)$ in the best case, and $O(n)$ in the worst case. Binary search is $O(1)$ in the best case, and $O(\log n)$ in the worst case.

If you simply ask “What is the time complexity of linear search?”, you get the answer “$O(n)$.” People say that because they have the worst case in mind. But why default to the worst case analysis? Because it gives us an upper bound on the running time. When we say linear search is $O(n)$, we are promising it will never do more than that on any input. That guarantee is often more useful than the best case, because the best case only happens on lucky inputs.

Not every algorithm has a split between best and worst case. Consider this code:

public int indexOfMin(int[] arr) {
  int minIndex = 0;
  for (int i = 1; i < arr.length; i++) {
    if (arr[i] < arr[minIndex]) {
      minIndex = i;
    }
  }
  return minIndex;
}

The indexOfMin method has no early return: even if the first element happens to be the smallest, you cannot know that until you have checked every other element. So it does $n-1$ comparisons on every input of size $n$, whatever the values are. Its best case and its worst case are the same, $O(n)$, so there is really just one case to report. Splitting best from worst only matters for an algorithm that does a different amount of work on different inputs, the way linear search and binary search do.