Counting steps: pseudocode and the machine we pretend to have

Before you can say one algorithm costs less than another, you have to agree what one step costs. That agreement is called a cost model.

Ask how long a procedure takes and the honest answer is a question: on what machine, with what compiler, with what else running? Timing a program measures the afternoon it was run on. To compare two algorithms and get an answer that survives next year's hardware, you count something the hardware cannot change.

What gets counted is the number of small, fixed-size actions the procedure performs. Here is a loop that adds up the numbers 0 up to n-1, with a counter that ticks once for each such action. Run it and look at how the tick count changes with n.

The counts are 53, 503 and 5003. Every pass through the loop costs five ticks, there are two ticks before the loop and one failed test at the end, so the count is $5n + 3$. Ten times the input, ten times the work, plus the same small constant.

Now change how finely you count. If an addition together with the assignment that stores it is called one action rather than two, then both total = total + i and i = i + 1 cost one tick each, and the per-pass cost drops from five (one test, two, two) to three (one test, one, one). The count becomes $3n + 3$. The 5 moved. What did not move is that the count is some constant times $n$, plus something small. That robustness is why this kind of counting is worth doing at all.

The RAM model

To count at all you need to agree which actions cost one unit. The standard agreement is called the RAM model, short for random access machine. It is a deliberately simple imaginary computer.

• Instructions run one after another. There is no second processor and nothing happens in the background.
• One arithmetic operation (add, subtract, multiply, divide, remainder), one comparison, one assignment, or one read or write of a single array cell at a known position each cost one unit of time.
• Any cell of memory can be reached in one unit of time, whichever cell it is. That is what random access means.
• Memory is unlimited and free to reach. There is no cache, no disk, and no cost difference between the cell you touched a moment ago and one far away.
• Control flow (entering a loop, taking a branch, calling a procedure) costs a constant number of units.

The word-RAM model adds one further condition, and it matters more than it looks. Memory is made of words, each holding a fixed number of bits, written $w$. A word is assumed wide enough to hold any index into the input and any input value, which for an input of size $n$ means $w$ is at least about $\log_2 n$ bits. Operations on whole words cost one unit.

The reason for that condition is practical. If a word could not hold an index, the procedure could not even name the position it was reading, and every array access would secretly cost more than one unit. If a word could hold arbitrarily large numbers, you could pack a whole array into one integer and do the work with one multiplication, which would make the model measure nothing.

Numbers that do not fit in a word break the one-unit assumption, and the two languages break it in opposite directions. Run this and see what your language does with a value far larger than a machine word.

In one language the arithmetic silently wrapped around, because the answer did not fit in 64 bits. In the other it stayed exact, because the language grows the number, and that growth costs time proportional to the number of digits. Either way, arithmetic on values that outgrow a word is not one unit, and an analysis that counts it as one is lying.

Pseudocode, and what it is for

Algorithms are usually written in pseudocode: code-shaped text meant for a human reader, with the language's ceremony removed so the method is visible. It is not runnable and is not meant to be. Here is the maximum scan from the previous lesson.

MAX(A, n)
  best = A[0]
  for i = 1 to n - 1
      if A[i] > best
          best = A[i]
  return best

• Indentation marks a block, exactly as in the snippets you run. There are no braces and no end.
• = means assignment and == means a comparison, so best = A[i] stores and A[i] > best asks.
• Arrays are indexed from 0 in this course, so an array of n entries has positions A[0] to A[n-1]. Some textbooks index from 1; when you read one, check which it does before trusting an index.
• for i = a to b includes both ends, so for i = 1 to n - 1 runs n - 1 times.
• // starts a comment. swap A[i], A[j] exchanges two entries and counts as a constant number of units.
• return stops the procedure immediately and hands back a value.

The model is wrong in known ways, and it is still the right tool. A real machine reads a cached value perhaps a hundred times faster than one from main memory, division is slower than addition, and allocating memory can take longer than a thousand additions. None of that changes whether a procedure does about $n$ operations or about $n^2$, and that difference is the one that decides whether the program finishes.