Measuring How Long a Program Takes
Efficiency is important, but it is secondary to correctness, and a program that is not correct is not efficient regardless of its speed.
Why a Fast Start Feels Like Progress
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.
What do you think happens?
When two programs are compared, which matters more: finishing fast, or giving the right answer?
Reveal answer
Giving the right answer matters more. Efficiency is important, but it is secondary to correctness.
A fast program produces its output sooner, and that output can look like progress. The source warns that this belief is easy to hold and that it is wrong: correctness is the first property to check, and speed is weighed after it.
This article explains what efficiency means in programming, why it matters, and why it must be weighed against correctness rather than placed above it. We will follow one judgment step by step, then look at the central question that time efficiency asks.
Correctness Comes First
Efficiency is important, but it is secondary to correctness, and a program that is not correct is not efficient regardless of its speed.
The reasoning in this definition works in one direction first. A fast program that gives wrong answers has not achieved anything meaningful. If 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.
Read the flowchart from the top. The correctness question comes before the speed question. A wrong answer ends the judgment at the first decision, no matter how fast the program ran. Only a program that passes the correctness check reaches the question about practical time.
The Reverse Failure: Correct but Too Slow
The ranking does not mean efficiency can be ignored. The source describes the reverse failure as just as 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 real efficiency problem.
Efficiency and Correctness Side by Side
Efficiency and correctness are two different properties of the same program. Each asks its own question, and each has a different place in the order of judgment. Placing them side by side makes the difference clear.
| Property | Question it asks | Priority |
|---|---|---|
| Efficiency | How long does the program take to do its task? | Important, but secondary to correctness |
| Correctness | Does the program produce the right result? | Comes first; a program that is not correct is not efficient |
Efficiency and correctness are different properties with different priorities.
Resources Efficiency Can Describe
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. All four sit under the single word efficiency, and each one names a different kind of resource a program might use well or wastefully.
A program can be efficient with one of these resources and wasteful with another. So when someone says a program is efficient, the useful follow-up question is which resource they mean.
Tracing One Judgment: Fast but Wrong Against Slow but Right
Judging two versions of the same program
Version A finishes in one second but gives wrong answers. Version B takes a minute but gives correct answers. Which one should be kept, and why?
- 1Check correctness first
Version A fails the first check. Its answers are wrong, so it is not efficient regardless of its speed.
- 2Stop the speed comparison
Because Version A fails, its one-second finish does not count in its favor. The comparison does not go further with it.
- 3Check Version B against correctness
Version B gives correct answers, so it passes the entry requirement.
- 4Ask whether its time is practical
Version B takes a minute. Whether that is acceptable depends on the task it was written for. If it is impractical, Version B still has a real efficiency problem to work on, but it is the version worth improving.
Version B is the one to keep and improve. Version A is not efficient, however fast it runs, because it does not do its job correctly.
Notice what this trace does not do. It never ranks the two versions by speed alone. The speed of Version A is real, but it is attached to a program that fails its job. That is the situation the source warns about when it says a program that is not correct is not efficient regardless of its speed.
The Central Question of Time Efficiency
Time efficiency refers to how long a program takes to execute. It asks how long a program takes to perform its task.
Notice that the question is phrased around a task. The analysis asks how long the program takes to do the job it was written for. It is not only asking how long one run happened to take on one occasion. Two questions usually sit next to it: how long does the program run, and is there another approach that will get the answer more quickly? Both ask the same thing from different angles, namely whether a better method exists for the same result.
Mistakes Beginners Make When Judging Speed
Common mistake Treating the faster program as the better one by default
What it looks likeA version that runs in a second is chosen over one that takes a minute, without checking either answer.
Why it failsSpeed says nothing about whether the output is right. A fast program that gives wrong answers is not efficient.
Do this insteadCheck correctness first, then ask whether the time is practical.
Common mistake Believing efficiency is more important than correctness
Why it failsThe source ranks efficiency as important but secondary to correctness.
Do this insteadTreat correctness as the entry requirement and efficiency as the measure of whether a correct program is usable.
Common mistake Ignoring efficiency once a program is correct
What it looks likeA correct program that takes ten thousand years is accepted as finished.
Why it failsA correct program that takes an impractically long time still has a real efficiency problem.
Do this insteadAfter correctness passes, keep asking whether the time is practical for the task.
Common mistake Using the word efficiency without saying which resource is meant
Practice: Ordering the Judgment
Program X returns a correct result in two minutes. Program Y returns a wrong result in less than a second. Program Z returns a correct result in a few seconds. Put the three programs in the order you would judge them, and explain in one sentence what the first check is for each.
Hints
- Start with the correctness check before comparing any times.
- A program that fails correctness is not efficient, whatever its speed.
- Only correct programs move on to the question of practical time.
Key Takeaways
- Efficiency matters, but it is secondary to correctness: a program that is not correct is not efficient regardless of its speed.
- A correct program that takes an impractically long time still has a real efficiency problem, so both properties must be considered.
- The word efficiency can refer to time, computer memory, disk space, or network bandwidth, so the resource in question should be named.
- Time efficiency asks how long a program takes to perform the task it was written for.