Understand syntax, logic and runtime errors and correct logic errors in algorithms; understand how the standard algorithms (bubble sort, merge sort, linear search, binary search) work; and use logical reasoning and test data to evaluate an algorithm's fitness for purpose and efficiency.

What this dot point is asking

This Edexcel point bundles three skills: classifying program errors (syntax, logic, runtime) and fixing logic errors; knowing how the four standard algorithms (bubble sort, merge sort, linear search, binary search) work; and evaluating an algorithm's efficiency using the number of comparisons, the number of passes through a loop and the use of memory.

Error types

The discriminators matter in the exam: syntax errors are caught by the translator before the program runs; logic errors are the hardest to find because the program runs happily but gives wrong answers, so a trace table is used to locate them; runtime errors appear only for certain inputs, which is why programs are tested with a range of test data. Correcting a logic error means changing the algorithm so it produces the right result, for example fixing a < that should be <=, or initialising a total to 0 instead of leaving it unset.

Searching algorithms

Linear search works on any list, sorted or not, but for $n$ items it may need up to $n$ comparisons. Binary search needs a sorted list but is far faster, needing at most about $\log_2 n$ comparisons, because each comparison halves the remaining items. For 1000 items, linear search may take up to 1000 checks but binary search takes at most about 10, since $\log_2 1000 \approx 10$.

Sorting algorithms

Bubble sort is simple to write but slow on large lists, because it may make many passes, each comparing most of the list. Merge sort is more complex (it uses the idea of decomposition, splitting then merging) but is much faster on large lists. Merge sort uses more memory because it creates the sublists during the splitting and merging, which is a typical efficiency trade-off: speed against memory.

Evaluating efficiency

Edexcel rewards quoting these measures with figures. Binary search beats linear search on comparisons (at most $\log_2 n$ versus up to $n$). Merge sort beats bubble sort on the number of passes for large lists, but bubble sort uses less memory. Using test data, including normal, boundary and invalid values, with logical reasoning about the expected output, is how you decide whether an algorithm is fit for purpose and where it could be made more efficient.

Try this

Q1. State one condition that must hold before a binary search can be used. [1 mark]

• Cue. The list must be sorted (in order).

Q2. State the type of error when a program runs but always outputs the wrong total. [1 mark]

• Cue. A logic error.