Welcome to Programming and Data Structures

An informal analysis of linear search is pretty straightforward. If we have a list of \(n\) items, we may have to check each item once to find the key. The work to check a single item is constant, so the total work is \(O(n)\text{.}\) Thus, we can say that linear search requires \(O(n)\) work in the worst case.

To analyze the efficiency of linear search in a more concrete way, we can examine the algorithm and do some accounting. The algorithm looks like this:

for (int i = 0; i < list.size(); i++) {
  if (list.at(i) == key) {
    return i;
  }
}
return -1;

All of the indexing and comparison operations are constant time. So:

for (int i = 0; i < list.size(); i++) {
  // O (1)
}
// O (1)

In this algorithm, the list size is \(n\text{,}\) so the loop runs \(n\) times. So:

loop O(n) times {
  // O (1)
}
// O (1)

Thus we have \(O(n) \cdot O(1) + O(1) = O(n) + O(1) = O(n)\) work in total if the loop runs to completion.

Of course we don’t always have to check all \(n\) items. If the key is at the beginning of the list, we check the first item and find what we are looking for. In this case, it does not matter how long the list is. The amount of work will be the same regardless of the length. That means it is \(O(1)\text{.}\)

What about the average case? If we are looking for a key that is equally likely to be at any position in the list, then sometimes we will check 1 item, sometimes 2 items, and so on, up to \(n\) items. The average number of items we check is therefore \((1 + 2 + ... + n) / n\text{.}\) That simplifies to \((n + 1) / 2\text{.}\)

Put simply, we check approximately half the items (\(n/2\) on average). Of course, in terms of Big-O, doing \(n\) units of work and doing \(n/2\) units of work are the same thing. They are both \(O(n)\text{.}\) Thus, the average case for linear search is also \(O(n)\text{.}\)