Linear Search Analysis

A linear search is one way to find some desired element (called the "key") in a given array or linked list. In a linear search, one starts at one end of the array, and compares each element of the array, in turn, until the key is found or one reaches the end of the array. An example of using a linear search to find the position of a given key in a given array is shown below. Note, there is no requirement that the elements of the array be in any particular order.

public static int positionOf(int[] list, int key) {
   for (int i = 0; i < list.length; i++)
       if (key == list[i])
           return i;  //found it! so return the position in the array and exit the method
   return -1;     //didn't find it, but we have to return something
}

For a linked list, the process is similar. We traverse the list, starting with its first element, until either the item sought is found or we reach the end of the list -- as suggested by the nodeWithItem() method below:

public class LinkedList {

   private class Node {
      Item item;
      Node next;
   }

   private Node first;

          ⋮

   public boolean nodeWithItem(Item item) {
      for (Node n = first; n != null; n = n.next) {
         if (n.item.equals(item)) return n;  // found it! so return reference to the 
                                             // node and exit the method
      }
      return null;  //didn't find it, so return null
   }
}

Consider the runtime analysis of such a method. How many comparisons we make between the key and array elements completely depends upon where the key lies in the array. If the key value is found at a position with a low index, it should be found quickly. If not, it may take a while. In the worst case, the key might be at the end of the array -- or not be in the array at all.

Supposing the length of the array is $n$, one must then potentially compare an array or list node element with the desired key value up to $n$ times.

So searching for an element of an array using a linear search is, in the worst case, $O(n)$.