3.1.2 - Comparing algorithm efficiency

Different solutions to one problem

More than one algorithm can solve the same problem. Before comparing efficiency, check that the methods solve the same task for the allowed inputs.

Suppose a challenge awards 1 point for level 1, 2 for level 2, and so on up to level n. The task is to calculate the total for completing every level from 1 to n, where n is a positive whole number.

One method starts a total at zero and adds each level's points:

total ← 0
FOR level ← 1 TO n
    total ← total + level
ENDFOR
OUTPUT total

For n = 6, the total changes through 0, 1, 3, 6, 10, 15 and 21. AQA's FOR includes both endpoints, so the body uses the values 1 to 6. The counter is declared in the FOR statement; it does not exist after the loop and does not take an extra value of 7.

A second method uses a calculation instead of adding each value separately:

total ← (n * (n + 1)) DIV 2
OUTPUT total

DIV means integer division. The product n * (n + 1) is always even for a whole-number n, so dividing it by two gives the exact whole-number total. For n = 6, this gives (6 × 7) DIV 2 = 21.

We can see why the calculation works by writing the six values forwards and backwards:

Together the two rows contain twice the required total. There are six column sums of seven, giving 42; halving gives 21. The same reasoning gives n column sums of n + 1. This is an explanation of this example's method, not a formula you must memorise for algorithm comparisons.

Both algorithms output the same total. An algorithm that outputs only n * n would be quicker to describe but wrong for this task: when n = 6, it gives 36. Correctness comes before efficiency.

Comparing work and time

Time efficiency concerns how long an algorithm takes to complete its task. You can often explain a difference by considering how much repeated work each method needs as the input changes.

The first method performs n additions to build the total, as well as controlling the loop. Increasing n from 6 to 1,000 increases those additions from 6 to 1,000. The second method still uses one addition, one multiplication and one integer division for the calculation. It does not process each level separately.

For a large n under comparable conditions, the second method is likely to take less time because it avoids the growing number of loop repetitions. A useful answer gives this reason, rather than simply calling the method “more efficient”. For a very small input the difference can be small, and different operations need not take exactly the same time.

The Python Study demonstration prints the total from both methods and counts only the additions used to build the loop's total. The extra counter and prints let us observe the work; they are not a measurement of the algorithms' running times.

Here range(1, n + 1) supplies Python with the values 1 through n, because Python excludes the range endpoint. Python's // performs integer division for these positive values. These are language details of the demonstration; the written pseudocode above uses AQA's inclusive FOR and DIV conventions.

If you compare actual running times, use the same task and comparable inputs and conditions. A slow computer, other running programs or added printing could affect an observation. One timing from a different machine does not by itself show that an algorithm requires more work.

For this specification, comparisons concern time efficiency; formal efficiency notation is not required. Explain the relevant steps, comparisons or repetitions and how they affect time. Later search and sort examples will let you compare methods whose performance also depends on the arrangement of the data.