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

Count comparisons to see how the cost of one algorithm depends on the input it receives.

#include <stdio.h>

static int comparisons = 0;

static int linear_search(const int *values, int n, int target) {
  for (int i = 0; i < n; i++) {
    comparisons++;
    if (values[i] == target) {
      return i;
    }
  }
  return -1;
}

int main(void) {
  int values[] = {7, 3, 9, 1, 5, 8, 2, 6};
  int n = (int)(sizeof values / sizeof values[0]);

  comparisons = 0;
  linear_search(values, n, 7);
  printf("best case: %d\n", comparisons);

  comparisons = 0;
  linear_search(values, n, 6);
  printf("worst case, last item: %d\n", comparisons);

  comparisons = 0;
  linear_search(values, n, 100);
  printf("absent: %d\n", comparisons);

  int total = 0;
  for (int i = 0; i < n; i++) {
    comparisons = 0;
    linear_search(values, n, values[i]);
    total += comparisons;
  }
  printf("average over present items: %.1f\n", (double)total / n);
  return 0;
}

Output

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 the particular input, not just its size. Linear search stops as soon as the target is found. Its best case is one comparison, when the target is the first item. Its worst case is n comparisons, when the target is last or missing.

For the average case you must state an assumption. If every item is equally likely to be the target, the expected number of comparisons is (1 + 2 + ... + n) / n = (n + 1) / 2. Counting comparisons with a variable gives exact, machine-independent numbers, unlike timing.

Explore the dry run

Guided walkthroughReady

1#include <stdio.h>

3static int comparisons = 0;

5static int linear_search(const int *values, int n, int target) {

6 for (int i = 0; i < n; i++) {

7 comparisons++;

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

9 return i;

10 }

11 }

12 return -1;

13}

15int main(void) {

16 int values[] = {7, 3, 9, 1, 5, 8, 2, 6};

17 int n = (int)(sizeof values / sizeof values[0]);

19 comparisons = 0;

20 linear_search(values, n, 7);

21 printf("best case: %d\n", comparisons);

23 comparisons = 0;

24 linear_search(values, n, 6);

25 printf("worst case, last item: %d\n", comparisons);

27 comparisons = 0;

28 linear_search(values, n, 100);

29 printf("absent: %d\n", comparisons);

31 int total = 0;

32 for (int i = 0; i < n; i++) {

33 comparisons = 0;

34 linear_search(values, n, values[i]);

35 total += comparisons;

36 }

37 printf("average over present items: %.1f\n", (double)total / n);

38 return 0;

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
Each loop pass is one comparison, counted in a global variable.	`—`	—
7 is the first item, so one comparison finds it.	`—`	best case: 1
A missing target forces all 8 items to be examined, the same as the worst case for a present item.	`—`	best case: 1 worst case, last item: 8 absent: 8
Searching once for each item costs 1 + 2 + ... + 8 = 36 comparisons, so the average is 36 / 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), average case (n + 1) / 2 comparisons, which is O(n).

Dividing two ints discards the fraction. Cast one operand to double first, as in (double)total / n.
Big O usually describes the worst case, but the average case can be much better. State which case you mean.

Try it yourself

What is the average number of comparisons for n = 100?

Reveal answer and reasoning

(100 + 1) / 2 = 50.5 comparisons when every item is equally likely.

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

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading