Trace Tables

Becoming the Computer

You have written some tidy pseudocode. It looks right. But looking right and being right are different things — the computer will execute what you wrote, not what you meant, with perfect obedience and zero common sense.

The tool for checking is the trace table: a table where you execute the algorithm yourself, one line at a time, recording the value of every variable as it changes. You become the computer — same rules, slower clock.

How to Build One

1. One column per variable, plus a column for any output (and, for loops with conditions, a column for the condition's true/false value)
2. Start at the first line and execute exactly what is written
3. Each time a value changes, write the new value on a fresh row
4. Continue until the algorithm ends

Rule 2 is the sacred one: no autopilot. If the code says x ← x * 3 and you feel sure the author meant + 3, trace the *. The gap between intended and written is precisely what you are hunting.

A Worked Example

This pseudocode should add up the numbers 1 to 4:

total ← 0
i ← 1
WHILE i <= 4
    total ← total + i
    i ← i + 1
ENDWHILE
OUTPUT total

The trace:

Line	total	i	i <= 4	Output
total ← 0	0
i ← 1	0	1
WHILE check	0	1	true
total ← total + i	1	1
i ← i + 1	1	2
WHILE check	1	2	true
total ← total + i	3	2
i ← i + 1	3	3
…	6	4	true
…	10	5	false
OUTPUT total	10	5		10

The loop body ran four times, the condition finally failed at i = 5, and the output is 10 = 1+2+3+4. The algorithm is confirmed correct — not by hope, but by evidence.

Catching a Real Bug

Now the same code with one tiny change: WHILE i < 4 instead of <=. Trace it and the condition fails at i = 4 — before adding the 4. Output: 6, not 10. The loop ran three times instead of four.

That is an off-by-one error, probably the most common bug in all of programming. Notice what the trace table did: it didn't just say "wrong answer" — it showed which turn of the loop went missing, pointing a finger straight at the <. That is debugging at its most surgical. Compare the alternative: staring at the code, which looks fine, because < and <= are easy for eyes to blur together.

Tracing at the Boundaries

Trace tables shine brightest on boundary cases — the extreme inputs where algorithms most often crack:

• What if the list is empty? (Does the loop body ever run? Does the algorithm output something sensible?)
• What if there is exactly one item?
• What if the target of a search is the first item — or the last — or absent entirely?

Professionals test programs with exactly these values, and a trace table is how you predict what should happen before running anything. It also deepens understanding: trace bubble sort once by hand and you will never again be fuzzy about how it works.

Try It Yourself

Trace this with inputs 5, 8, 3 (columns: n, biggest, output):

biggest ← 0
FOR each of 3 turns
    INPUT n
    IF n > biggest THEN biggest ← n
NEXT
OUTPUT biggest

You should get 8. Now the sharper question, courtesy of boundaries: what does it output if the inputs are −5, −8, −3 — and is that answer right? (Your trace will reveal a genuine design bug: starting biggest at 0 fails for all-negative inputs. Better: start it with the first input.)

Worked Example — Tracing a Nested Structure

Trace tables prove their worth most clearly on nested structures, where it is easy to lose track of which counter is doing what. Trace this small nested loop, which should print a multiplication fact for each combination:

FOR row ← 1 TO 2
    FOR col ← 1 TO 2
        result ← row * col
        OUTPUT row, " x ", col, " = ", result
    NEXT col
NEXT row

row	col	result	Output
1	1	1	"1 x 1 = 1"
1	2	2	"1 x 2 = 2"
2	1	2	"2 x 1 = 2"
2	2	4	"2 x 2 = 4"

Watch the columns carefully: col completes both its values (1, then 2) for every single value of row — exactly the "fast hand, slow hand" behaviour described in nested structures — while row only changes once the inner loop has fully finished. Building this table one row at a time, rather than trying to picture the whole nested loop in your head at once, is precisely why trace tables exist: they turn something genuinely hard to hold in working memory into a small, mechanical, unmissable record.

Key Words

• Trace table — a step-by-step record of variable values while hand-running an algorithm
• Trace — to execute code by hand, exactly as written
• Off-by-one error — a loop or index that runs one time too many or too few
• Boundary case — an extreme input (empty, single, largest, negative) where bugs concentrate
• Dry run — another name for tracing without a computer