C++: best, worst, and average case of linear search

Count comparisons to see that one algorithm can have different costs on different inputs.

#include <iostream>
#include <vector>

int comparisons = 0;

int linear_search(const std::vector<int>& values, int target) {
  for (std::size_t i = 0; i < values.size(); ++i) {
    ++comparisons;
    if (values[i] == target) {
      return static_cast<int>(i);
    }
  }
  return -1;
}

int main() {
  std::vector<int> values = {7, 3, 9, 1, 5, 8, 2, 6};
  int n = static_cast<int>(values.size());

  comparisons = 0;
  linear_search(values, 7);
  std::cout << "best case: " << comparisons << "\n";

  comparisons = 0;
  linear_search(values, 6);
  std::cout << "worst case, last item: " << comparisons << "\n";

  comparisons = 0;
  linear_search(values, 100);
  std::cout << "absent: " << comparisons << "\n";

  int total = 0;
  for (int v : values) {
    comparisons = 0;
    linear_search(values, v);
    total += comparisons;
  }
  std::cout << "average over present items: " << static_cast<double>(total) / n << "\n";
}

best case: 1
worst case, last item: 8
absent: 8
average over present items: 4.5

Explanation

The running time of an algorithm often depends on which input of a given size it receives. Linear search stops as soon as it finds the target, so its best case is one comparison, when the target is first. Its worst case is n comparisons, when the target is last or absent.

The average case needs an assumption about the input. If every present item is equally likely to be searched for, the expected number of comparisons is (1 + 2 + ... + n) / n, which is (n + 1) / 2. The program counts comparisons directly so the numbers do not depend on the machine.

—

best case: 1

best case: 1
worst case, last item: 8
absent: 8

best case: 1
worst case, last item: 8
absent: 8
average over present items: 4.5

Cost and common mistakes

Best case O(1), worst case O(n), and average case about n/2 comparisons, which is O(n).

• Big O is usually quoted for the worst case, but the average case can be far better. Always say which case you mean.
• The average depends on the distribution of inputs. If the target is usually absent, the average is close to n.

Try it yourself

What is the average number of comparisons for n = 100 when every item is equally likely?

Further reading

• C++ reference (cppreference) (external)
• C++ working draft (external)
• Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) (external)