To compare two algorithms fairly, write the contract first, then trace both on the same inputs. The better algorithm is the one that keeps the contract on every input, not the one that looks neater.
This lesson sits in algorithm reasoning and test design. It relies on the tracing skills from tracing pseudocode step by step.
What is the contract?
The task is to find the largest of three whole numbers a, b and c. The contract says: input three whole numbers; output the largest; if two or more tie for largest, output that value.
Write this down before you read either algorithm. It gives you a fixed yardstick.
What do the two algorithms look like?
Algorithm P
IF a > b AND a > c THEN
OUTPUT a
ELSE IF b > a AND b > c THEN
OUTPUT b
ELSE
OUTPUT c
END IFAlgorithm Q
SET largest = a
IF b > largest THEN
SET largest = b
END IF
IF c > largest THEN
SET largest = c
END IF
OUTPUT largestHow do you trace both on shared data?
Choose inputs that include a normal case and a tie. Use (4, 9, 6) and (8, 8, 3).
| Input | Expected | P gives | Q gives |
|---|---|---|---|
| 4, 9, 6 | 9 | 9 | 9 |
| 8, 8, 3 | 8 | 3 | 8 |
For (8, 8, 3) in Algorithm P, the first test 8 > 8 is false, so it moves on. The second test 8 > 8 is also false, so the ELSE branch runs and outputs c, which is 3.
Algorithm Q starts with largest = 8, finds 8 > 8 false, finds 3 > 8 false, and outputs 8. It meets the contract.
What is the lesson in this comparison?
The normal input cannot tell the two apart. The tie did, because Algorithm P uses strict >, so every tie between a and b falls through to the final ELSE.
| Question | Answer |
|---|---|
| Which algorithm is correct? | Q meets the contract on both inputs |
| Why does P fail? | Ties between a and b fall to the ELSE branch |
| Could P be repaired? | Yes, by using >= in both conditions |
Do not pick the algorithm that feels familiar. Only the traces count as evidence.
Check yourself
Algorithm R finds the smaller of two numbers x and y.
IF x < y THEN
OUTPUT x
ELSE
OUTPUT y
END IFDoes R meet the contract “output the smaller; if equal, output either”? Test it on (5, 5) and (7, 2).
Answer
For (7, 2): 7 < 2 is false, so the ELSE branch outputs y, which is 2. Correct.
For (5, 5): 5 < 5 is false, so ELSE outputs y = 5. The contract allows either value when they are equal, so this is also correct.
Algorithm R meets the contract on both inputs.
What to study next
Next, learn how checking a program differs depending on its purpose in separating validation from verification. Practise the tracing itself with the restricted pseudocode trace trainer.
If you want a teacher to go through your own comparisons, see online one-to-one Computer Science tuition.