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

Before you start

C++ vectors and functions.

Count comparisons to see that one algorithm can have different costs on different inputs.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

C++

#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";
}

Output

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <iostream>

2#include <vector>

4int comparisons = 0;

6int linear_search(const std::vector<int>& values, int target) {

7 for (std::size_t i = 0; i < values.size(); ++i) {

8 ++comparisons;

9 if (values[i] == target) {

10 return static_cast<int>(i);

11 }

12 }

13 return -1;

14}

16int main() {

17 std::vector<int> values = {7, 3, 9, 1, 5, 8, 2, 6};

18 int n = static_cast<int>(values.size());

20 comparisons = 0;

21 linear_search(values, 7);

22 std::cout << "best case: " << comparisons << "\n";

24 comparisons = 0;

25 linear_search(values, 6);

26 std::cout << "worst case, last item: " << comparisons << "\n";

28 comparisons = 0;

29 linear_search(values, 100);

30 std::cout << "absent: " << comparisons << "\n";

32 int total = 0;

33 for (int v : values) {

34 comparisons = 0;

35 linear_search(values, v);

36 total += comparisons;

37 }

38 std::cout << "average over present items: " << static_cast<double>(total) / n << "\n";

39}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
7 is the first item, so one comparison finds it.	`comparisons = 1`	—
Best case: 1.	`comparisons = 1`	best case: 1
An absent target forces the loop to examine all 8 items.	`comparisons = 8`	best case: 1 worst case, last item: 8 absent: 8
Searching for each item once costs 1 + 2 + ... + 8 = 36 comparisons, so the average is 36 / 8.	`total = 36`	best case: 1 worst case, last item: 8 absent: 8 average over present items: 4.5

Behind the scenes

How C++ processes this code

The C++ compiler produces a native executable. Execution enters main, where objects and function calls perform the work.

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?

Reveal answer and reasoning

(100 + 1) / 2 = 50.5 comparisons.