Why We Need a Way to Analyze Algorithms

In the last chapter, I claimed binary search is faster than linear search. I backed it up with a count of the number of comparisons each algorithm performs. Linear search, in the worst case, makes about $n$ comparisons; binary search makes about ${\log }_{2}n$. We compared the two counts, and the gap between them grows as $n$ grows.

Counting comparisons worked. But it was a shortcut. Look at the code for linear search again:

public static boolean linearSearch(int[] arr, int target) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
      return true;
    }
  }
  return false;
}

The comparison arr[i] == target is in there, but it is one operation among several. The loop declares and initializes i. On every pass it checks i < arr.length, reads arr[i], runs the if, and increments i. There is a return at the end. We counted the comparisons and ignored all the rest.

So why did I focus on arr[i] == target? Every one of those other operations happens once per pass through the loop. So does the comparison. If the loop makes 10 passes, the comparison happens 10 times, and the check i < arr.length happens 10 times, and the increment happens 10 times. Counting the comparisons tells us the number of passes, and every other operation in the body happens once per pass. That is why the one comparison can stand in for the whole loop body. In the worst case the loop makes $n$ passes, where $n$ is the length of the array, so the comparison happens $n$ times.

If we want to be more careful, we can count each operation separately:

So the total work is about $3n+3$ steps. The i < arr.length happens $n$ times for the loop, and one more time when the loop exits. Does that one extra check matter? Not really. If you look more closely, you can find even more steps that I skipped. None of the rows in the table is really one step. The int i = 0 is a declaration and an assignment. The i < arr.length is a comparison, but it also reads arr.length and reads i. The arr[i] == target is a comparison, but it also reads arr[i] and reads target. The i++ is an increment, but it also reads i, adds 1, and writes the result back to i.

If you wanted to be really precise, you would have to look at the bytecode that the Java compiler produces for this method, and count the actual instructions. Even then, you would have to see how each bytecode instruction translates to the machine code that the processor runs, and count those instructions too. Even then, two machine instructions do not necessarily cost the same. They do not always take the same amount of time, so you would have to look at the microarchitecture of the processor and count the cycles each instruction takes. You could keep counting in more and more detail, and it is not clear you would learn anything new by doing so.

However you count it, you end up with an expression of the form $\alpha n+\beta$ for some constants $\alpha$ and $\beta$. Where you stop counting decides what $\alpha$ and $\beta$ are, but it does not change the fact that the work is proportional to $n$. The $\alpha n+\beta$ is a linear function of $n$. That is a fact about the algorithm, not about the machine or the compiler. That is the part we want to keep.

Counting the comparisons in binary search gave us $\log n$ instead. We can compare linear to logarithmic without knowing $\alpha$ or $\beta$ at all, and that contrast already tells us the work of linear search grows much faster than the work of binary search as the input grows.

In this chapter we will develop a general method for analyzing algorithms. It captures the relationship between the work an algorithm does (the steps it takes toward completion) and the size of the input, without having to count individual operations. This method is called asymptotic analysis.