Correctness of Programs

Many beginning programmers judge a program by how quickly it finishes. If one version runs in a second and another takes a minute, the faster one feels like the better one. This instinct is natural, and it is also the source of a common mistake. Speed is a real property worth studying, but it is not the first property we should check. Before asking how fast a program is, we should ask whether it does its job at all.

Consider two hypothetical programs written for the same task. Program A finishes in one second but returns the wrong answer. Program B takes a full minute but returns the correct answer. Follow each one through the two questions a careful reviewer asks, in order: does it do its job, and then how fast does it do it?

Program A wins on speed, but that win does not make it efficient. Its speed was obtained by failing the one thing it was supposed to deliver. Program B is slower, yet it has actually done the job. The source's position is that a program that is not correct is not efficient regardless of its speed, so Program B is the one that can be called efficient in the sense that matters, and it still must be judged on how long that minute is compared with what the task needs.

The source ranks these two concerns clearly. Efficiency is important, but it is secondary to correctness. The reasoning works in both directions, and it is worth looking at each direction separately.

In the first direction, suppose you do not care whether a program works. You can make it run very quickly indeed, but nobody would consider that a meaningful achievement. The speed was bought by giving up the one thing the program was supposed to deliver.

The reverse failure is also real. A program that produces a correct answer after ten thousand years is not very useful either. So efficiency is not optional. A correct program that takes an impractically long time still has a problem.

The difference between the belief most learners start with and the correct order of evaluation is easiest to see by tracing what happens to the same fast, wrong program under each ordering. Under the speed-first habit, the program passes because it finishes quickly. Under the correctness-first habit, the program is stopped before its speed is ever considered.

The word efficiency is broader than speed. It can describe the efficient use of almost any resource a computer has. The source names four: time, computer memory, disk space, and network bandwidth. A program can be efficient with one of these and wasteful with another, so when someone says a program is efficient, the useful follow-up question is which resource they mean.

This article, and the analysis that follows it in the chapter, concentrates on time efficiency. Time efficiency refers to how long a program takes to execute. Keeping one resource in focus makes the analysis manageable, and the source explicitly limits itself to this case.

Notice that the question is phrased around a task, not around the program's code or its raw speed in isolation. The two follow-up questions, how long the program runs and whether a better method exists, both ask the same thing from different angles: whether a better method exists for the same result.