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

Before you start

C arrays, functions, and loops.

Count comparisons to see how the cost of one algorithm depends on the input it receives.
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 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.

Code example

#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

Example details

Follow the code

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

Show guided walkthrough

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

Behind the scenes

How C processes this code

The C compiler produces a native program. Variables occupy memory, and execution enters main.

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.