Cambridge Syllabus Notes

Algorithm Design & Problem‑Solving: Trace Tables

What is a Trace Table? 🍽️

Think of a trace table as a recipe card for an algorithm. Just like a recipe lists ingredients and steps, a trace table lists all the variables and shows how they change step by step.

When you dry‑run an algorithm, you pretend to run it with a specific input and record every change. The trace table keeps that record tidy.

How to Create a Trace Table

List all variables in the first column.
Write the initial values (before the algorithm starts).
For each line of the algorithm, add a new row and update the variables that change.
Use clear labels like Step 1, Step 2, …
Double‑check that every update matches the algorithm’s logic.

Example Algorithm: Sum of the First n Natural Numbers

Algorithm (pseudo‑code):


sum ← 0
i ← 1
while i ≤ n do
    sum ← sum + i
    i ← i + 1
end while

Let’s dry‑run this with n = 4 and create a trace table.

Step	i	sum
Initial	1	0
1	1	1
2	2	3
3	3	6
4	4	10

Result: sum = 10, which matches the formula $1 + 2 + 3 + 4 = 10$.

Exam Tips 📚

Always label each step clearly.
Show initial values before the first step.
Include all variables even if they don’t change in a step.
Use consistent formatting – it makes the table easier to read.
Double‑check that the final value matches the expected output.

Practice Exercise

Try creating a trace table for the following algorithm that calculates the factorial of n:


fact ← 1
i ← 1
while i ≤ n do
    fact ← fact × i
    i ← i + 1
end while

Use n = 5 for your dry‑run. Good luck! 🚀

Complete a trace table to document a dry-run of an algorithm