Key Stage 3 computing · Algorithms

KS3 computing: comparing algorithms and choosing the best

Several different algorithms can solve the same problem, and at Key Stage 3 students learn to decide which is better for a particular job. They compare algorithms by counting steps, testing best and worst cases, and weighing up trade-offs such as speed, simplicity and the state of the data. This is reasoning rather than guessing, and it is at the centre of computer science.

Comparing algorithms, explained

The national curriculum asks Key Stage 3 pupils to understand several key algorithms and to use logical reasoning to compare the utility of alternative algorithms for the same problem. “Utility” just means usefulness. Students are not asked to find the single best algorithm in the world, but to give reasons for which one suits a situation, using evidence. The usual examples come from searching and sorting, which are explained on their own pages, but the thinking applies to any problem with more than one solution.

The first question is whether an algorithm is correct: does it always give the right answer, including in awkward cases such as an empty list, a single item or repeated values? Only then do students ask how efficient it is. Because the time a program takes depends on the computer, students usually count steps instead, such as comparisons or swaps, using a trace table or a counter in code. Running the same algorithm on lists of 10, 100 and 1,000 items shows how the amount of work grows as the data grows, which matters more than the speed on a single test.

Students are taught to look at the best case, the worst case and the typical case. A linear search is fastest when the item is first and slowest when it is last or absent. They also look at assumptions: binary search is fast, but only on sorted data. And they consider other costs, such as how much memory is used, how hard the algorithm is to write and check, and how often the data changes. The best choice often depends on a trade-off, and a simple algorithm can be the right answer for a small problem.

Good reasoning has a clear shape: state the problem, list the options, test them on the same data, compare using measured evidence, and finish with a conclusion that names the conditions. Students practise this in written explanations, tables comparing the options and short programs that count steps. Formal efficiency notation is left to later study. At this stage the aim is for them to say “this one because…” and be able to back it up.

Words your child will hear

Efficiency: How much time, memory or effort an algorithm needs to do its job.
Correctness: Whether an algorithm always gives the right answer, including in unusual cases.
Best case and worst case: The least and most work an algorithm may need for a given size of problem.
Trade-off: Gaining something, such as speed, by giving up something else, such as simplicity.
Test data: Chosen inputs used to check an algorithm, including normal, extreme and awkward cases.
Trace table: A table showing how values change as an algorithm runs, so steps can be counted.
Utility: How useful something is for a particular purpose.

What the National Curriculum says

The programme of study for Key Stage 3 says:

Pupils should be taught to understand several key algorithms that reflect computational thinking [for example, ones for sorting and searching]; use logical reasoning to compare the utility of alternative algorithms for the same problem
Aim: pupils can analyse problems in computational terms, and have repeated practical experience of writing computer programs in order to solve such problems.

Objectives from the National Curriculum in England, © Crown copyright, used under the Open Government Licence v3.0.

Try it: choosing how a school stores pupil records

A school has 1,200 pupil records. Staff look up a pupil dozens of times a day, and new pupils are added only a few times a term. Should the records be kept in no particular order and searched with linear search, or kept sorted by surname and searched with binary search?

State what each option does. Linear search checks records one at a time and works on any order. Binary search halves the remaining records each time but needs them sorted by surname.
Count the steps for a look-up. Linear search needs up to 1,200 checks, and about 600 on average if the pupil is equally likely to be anywhere. Binary search needs at most 11 checks, because each check halves the records still in play and 1,200 runs out within 11 halvings.
```
Linear:  up to 1200 checks
Binary:  up to 11 checks
```
Count the steps for adding a pupil. In an unsorted list, a new record goes on the end, which is one step. In a sorted list, it must be placed in the right position, which means finding the spot and shifting later records along, around 600 moves on average.
```
Unsorted add:  1 step
Sorted add:    ~600 moves
```
Weigh them against how the data is used. Look-ups happen dozens of times a day, and additions only a few times a term. Paying a cost for each addition is worth it if it saves hundreds of checks on every look-up.
Check the assumptions and test. The reasoning holds only while the list stays sorted, so correctness depends on inserting new pupils in the right place. Test with a name at the start, the end, one that is missing and two pupils with the same surname. A very short list would not justify the extra care.

Keep the records sorted and use binary search. The saving of hundreds of checks per look-up outweighs the extra work when adding a pupil, because look-ups are far more frequent. If records were added all day and rarely searched, the answer could be the opposite.

Common mistakes and how to help

Judging an algorithm by how fast it ran on one test

Timing a program on one list on one computer is easy, so students trust it, but small data can hide big differences and other tasks affect the clock.

What helps: Count steps, and run each algorithm on small, medium and large inputs. Look at how the count grows, not just a single number.

Believing the algorithm with fewer steps is always the best

Step counts are easy to compare, so other qualities are overlooked, such as readability, memory use and the effort of keeping data sorted.

What helps: Ask “best for what, and under which conditions?” A simple method that is easy to check can beat a clever one on small or changing data.

Testing only normal data

Students check a typical case, see the right answer and conclude that the algorithm works.

What helps: Always include extreme cases (empty, one item, the largest size) and awkward ones (duplicates, the item missing, data already in order or in reverse).

Giving an opinion instead of a reason

“Binary search is better because it is faster” sounds right, but it has no evidence or conditions behind it.

What helps: Use a sentence frame: “For this problem, I would choose … because … The evidence is … This would change if …” This turns a claim into reasoning.

How to help at home

Compare two ways to do a chore. Ask your teenager to think of two ways to find a missing sock or tidy a shelf, and to decide which is better and why. Giving reasons for a choice is the skill being taught.
Play a guessing game and count. Guess a number from 1 to 100, once by guessing 1, 2, 3 and once by halving each time. Count the guesses for several secret numbers and talk about the best and worst cases.
Ask the “what would change your mind” question. When your child recommends a method, ask what would make a different method better. Naming the conditions is the difference between a reason and an opinion.
Look for trade-offs in everyday choices. A quicker route may be more expensive, and a cheaper phone plan may have less data. Discuss how a choice depends on what matters most, which is exactly how algorithms are chosen.
Review their test data. If they are writing a program for homework, ask what test cases they chose. A short list that includes the smallest, largest and strangest inputs is a sign of careful thinking.

Builds on

Key Stage 2: Designing, writing and debugging programs
Key Stage 2: Controlling and simulating physical systems
Key Stage 2: Decomposition: breaking problems down
Key Stage 2: Sequence in programs
Key Stage 2: Selection: if and else
Key Stage 2: Repetition and loops
Key Stage 2: Variables, input and output
Key Stage 2: Explaining how algorithms work
Key Stage 2: Debugging algorithms and programs