Best Case Time Complexity

While Big O notation typically describes the worst-case time complexity of an algorithm, in some situations, it can be useful to consider the best-case complexity.

When the Best Case is Likely

If the input data for your algorithm is often in a form that triggers the best-case performance, then the best case might be more relevant than the worst case. For example:

1int linearSearch(int arr[], int n, int x) {
2  for (int i = 0; i < n; i++) {
3    if (arr[i] == x)
4      return i;
5  }
6  return -1;
7}

Linear search has a best-case complexity of $O(1)$ if the element is found at the first position. If the input data is often sorted or if the searched-for element is often at the beginning, this best-case performance might be more relevant.

When the Worst Case is Unacceptable

In some critical systems, the worst-case performance might be catastrophic, even if it's unlikely. In such cases, you might need to ensure that even the worst case is acceptable.

When Comparing Algorithms

When choosing between different algorithms for a problem, considering the best, average, and worst cases can give a more complete picture than just the worst case.

Optimistic Algorithms

Some algorithms are designed to take advantage of best-case scenarios. These are known as optimistic algorithms. They hope for the best but prepare for the worst.

An example is the Quicksort algorithm, which has a best-case complexity of $O(n log n)$ when the pivot always splits the array in the middle, but a worst-case complexity of $O(n^2)$ when the pivot is always the smallest or largest element.

However, in most cases, worst-case complexity is more important, as it gives an upper bound on the running time. Average-case complexity is also often more practical than best-case complexity. But understanding all three can provide a fuller picture of an algorithm's performance characteristics.