Why We Suppress Coefficients

Recall the earlier section in this chapter where I tried to count the work of linear search. I first said that the work is about $3n+3$ steps, and then I realized that if I count more precisely, depending on the level of abstraction I choose, I can find more steps, but the work is still about $\alpha n+\beta$ steps for some constants $\alpha$ and $\beta$. That is already one argument for suppressing coefficients. The values of $\alpha$ and $\beta$ depend on many factors, such as the machine, the language, the compiler, and so on. We may as well ignore them since all those factors are external to the algorithm itself.

There is a second argument, and this one does not involve the machine. Even on the same machine with the same compiler, the coefficients change when you write the same algorithm a different way. Here is a contrived example.

public void countUp(int num) {
  for (int i = 1; i <= num; i++) {
    System.out.println(i);
  }
}

public void countUp(int num) {
  int count = 1;
  for (int i = 0; i < num * 2; i+=2) {
    System.out.println(count++);
  }
}

public void countUp(int num) {
  int count = 1;
  int upper = num * 2;
  for (int i = 1; i <= upper; i+=2) {
    System.out.println(count++);
  }
}

The three versions of countUp do the same thing: they print the numbers from 1 to num. But they do it in different ways, and that leads to different counts of steps.

Let’s make a simplifying assumption that each simple operation (like i++, count++, i < num * 2, i <= upper, etc.) takes one step, and each call to System.out.println takes one step. Then we can count the number of steps for each program as follows (writing $n$ for num):

The coefficient of $n$ and the constant term are different in all three programs, even though the three programs do the same thing. The algorithm did not change here (broadly speaking). Only the way the code was written changed, and that changed the total from $3n+2$ to $5n+4$ to $4n+4$.

So the coefficients depend on the machine, the language, the compiler, and the coding style. They do not depend on the algorithm. That is why we suppress them. We set both $\alpha$ and $\beta$ to $1$, and all three totals become $n+1$.