Counting steps instead of seconds
Why a stopwatch is the wrong tool for understanding a structure, and what to count instead.
Suppose you have two ways of doing the same job and you want to know which is better. The obvious approach is to time them. Run both, watch the clock, keep the winner. There is nothing wrong with that, and eventually you should do it. But as a way of understanding what is going on, it is surprisingly unhelpful.
The trouble with the stopwatch
A measured time is not a fact about the method. It is a fact about the method, plus the machine, plus the programming language, plus whatever else the computer was busy with at that moment, plus how warm the laptop was and whether it was running on battery. Change any of those and the number changes. Sometimes the ranking changes too.
There is also a more practical problem. You usually want to know how something will behave with a million records, and you are testing with fifty. The stopwatch has nothing at all to say about that.
Counting instead
So we count steps rather than measuring seconds. A step is one small piece of work: comparing two values, moving one item, following one pointer, doing one bit of arithmetic. It is deliberately vague, and that turns out not to matter, for a reason that will become clear shortly.
Let us count something real. You have a list of names in no particular order and you are looking for one specific name. You have no choice but to check them one at a time from the start.
Change wanted to "Ada", then to "Eve", then to "Zed", running it each time. Which name costs the most checks, and why does a name that is not there cost that much?
A name at the front costs one check, a name at the back costs ten, and a name that is not there costs ten as well, because the only way to be sure it is absent is to have looked at all of them. The table below says the same thing for longer lists.
| How many names | If it is first | If it is last | Typical, if it is somewhere |
|---|---|---|---|
| 10 | 1 check | 10 checks | about 5 checks |
| 20 | 1 check | 20 checks | about 10 checks |
| 40 | 1 check | 40 checks | about 20 checks |
| 80 | 1 check | 80 checks | about 40 checks |
| 1,000 | 1 check | 1,000 checks | about 500 checks |
Read down the first four rows. Each one doubles the length of the list, and each one doubles the numbers in the last two columns: 10, then 20, then 40, then 80. The 1,000 row is there to show the same rule still holding at a size you would not want to check by hand. That relationship holds on any machine, in any language, in any year. It is a fact about the method itself, which is exactly what the stopwatch could not give us.
Calling it n
We need a short way to say however many items there are, because we want to talk about the pattern rather than any one list length. The letter n is used for that throughout the subject. When you read "a list of n items", read it as "a list of however many items, call it n".
With that word in hand, the table above says something compact: searching this way takes up to n checks. If n is 40 that is 40 checks. If n is a million it is a million checks.
You replace your laptop with one twice as fast. Does the count of steps for searching a list of 1,000 names change?
No. It is still up to 1,000 checks, because the method has not changed. What changes is how many seconds those checks take. That is precisely why we count steps: the count describes the method, and the seconds describe the machine.