What is an Algorithm?

Given a dynamic array, how do we find out whether it holds a particular value?

The elements sit in slots 0 through size - 1, in no particular order. Nothing about the layout tells us where a given value might be, so there is no arithmetic we can do to jump to it the way get jumps to an index. The only thing left is to look at the elements one at a time and compare each one against the value we want.

So we iterate from left to right. If we find a match, we can stop and say yes. If we get all the way to the end without a match, we have checked every element, and now we can say no. Notice that we can only answer “no” at the very end. Any element we have not looked at yet could be a match.

Here is that as a method:

public boolean contains(int value) {
  for (int i = 0; i < size; i++) {
    if (arr[i] == value) {
      return true;  // found it
    }
  }
  return false;  // checked every element, no match
}

Note the loop runs up to size, not arr.length. Only the first size slots hold real elements, and the rest are unused space. If we looped to arr.length we would compare the value against leftover slots that hold 0, and contains(0) would return true on an empty array.

This technique, scanning one element at a time until we find the value we want, is called linear search. It is an example of an algorithm.

Defining “algorithm”

An algorithm is a step-by-step procedure for solving a problem. Linear search solves the problem “is this value present?” with a precise sequence of steps.

Linear search is not the only algorithm we have seen. Every operation we have written is an algorithm. add is one for appending a value. grow is one for moving elements into a larger backing array. get and set are algorithms for reading and overwriting at an index. Each one is a finite sequence of steps that solves a specific problem.

We expect a few things from any procedure before we will call it an algorithm:

• Unambiguous steps. Each step is precise, with no room for interpretation, and can actually be carried out.
• Definite order. The steps happen in a well-defined sequence.
• Finite. It terminates after a finite number of steps rather than running forever.
• Well-defined input and output. It takes a clear set of inputs and produces a result, so we can reason about whether it is correct.

Check linear search against all four. Each step is a comparison and an increment, so the steps are unambiguous. The loop fixes the order. The loop is guaranteed to end, because size is a finite number and i increases every pass. And the input is a value and a collection, and the output is true or false. So linear search is an algorithm.

The cost of contains

We saw with add that the same operation can cost differently depending on the situation. contains is like that too, but for a different reason: if the target value is the first element, we find it quickly in the first iteration of the loop, no matter how large the array is. On the other hand, if the value is not present at all, we have to check every element before we can say no. This work grows with the size of the array.

In both add and contains, the cost varies depending on the specific circumstances.

• Best case: the circumstances are optimal, leading to the least amount of work.
• Worst case: the circumstances are abysmal, leading to the most work.

The variation comes from a different place in each case. For add, it depends on how full the backing array happens to be. In the worst case, the array is full and we have to grow it. For contains, it depends on where the value sits. In the worst case, the target value is at the end of the array, or not there at all.

Make a note of the idea that the work grows with the size of the array. We will come back to this idea in the chapter on efficiency. There, we will describe the relationship between the size of the input and the amount of work required. For now the point is that “how much work does this take?” is a real question we can ask about any algorithm.