Trace Tables & Efficiency (Years 10–11) — Computer Science

Using trace tables to follow variables step by step, and describing how an algorithm's work grows with input size.

A pilot does not just trust the plane — they run a checklist, watching each dial change as they flip each switch. When your program misbehaves and you cannot see why, you do the same: you become the computer and step through the code line by line, writing down every variable as it changes. That written record is a trace table, and it is the single most powerful tool for understanding — and debugging — an algorithm by hand.

Why this matters: Trace tables prove exactly what code does, catching bugs a quick read misses. And once you can trace an algorithm, you can count its steps — the first move towards judging its efficiency, which decides whether software feels instant or painfully slow.

As data grows, an n² algorithm's effort explodes while log n barely rises.

What a trace table is

A trace table: the paper acts as the computer's memory.

A trace table has one column per variable (plus a column for any output) and one row per change. You execute the algorithm in your head, and each time a variable is updated you write its new value in a fresh row. Nothing is remembered in your head — the table is the memory.

Tracing a loop, step by step

Each loop turn adds one row: the No branch repeats, Yes exits.

Consider this pseudocode that sums 1 to 3:

total = 0
FOR i ← 1 TO 3
    total = total + i
NEXT i
OUTPUT total

i	total	OUTPUT
–	0
1	1
2	3
3	6	6

Reading down the total column shows exactly how the answer builds: 0, 1, 3, 6. If a bug gave 5, the wrong row tells you which step broke.

Measuring efficiency

The efficiency ladder: lower on the ladder means less work as n grows.

Efficiency asks: how does the work grow as the input grows? We describe it with the input size n. Think of it as an analogy: a bigger crowd is easy to count (linear) but very hard to make everyone shake hands with everyone (quadratic).

Constant — same work whatever n is (grab the first item).
Logarithmic (log n) — grows very slowly, e.g. binary search.
Linear (n) — grows in step with n, e.g. linear search.
Quadratic (n²) — grows steeply, e.g. bubble sort.

Worked reasoning: Linear search on 10 items may take up to 10 checks; on 1,000 items, up to 1,000 — the effort tenfolds when the data tenfolds, so it is linear. Binary search goes from about 4 checks to about 10 for the same jump — barely more, because it is logarithmic.

Common mistake: Only writing the final value of a variable in a trace table. You must record every change on its own row — the whole point is to see the journey, not just the destination.

Memory hook: Trace = one row per change. For efficiency, remember the ladder constant < log n < n < n² — lower is faster.