Fitness for purpose

An algorithm can be evaluated only when its requirements are clear. A requirement states what the algorithm must do for permitted inputs; it may also include limits such as how much memory is available.

Fitness is the judgement; test data provides evidence for that judgement.

Logical reasoning connects the requirement to a judgement:

1. Derive the expected result from the requirement.
2. Follow the algorithm with the chosen input to derive its predicted result.
3. Compare expected with predicted.
4. Use the evidence to judge fitness for purpose.

Choose test values that can separate a correct algorithm from a nearly correct one. For a threshold, try values below, exactly at and above it. For an algorithm that examines a list, useful cases can place the important item first, in the middle, last or not in the list, provided these inputs are permitted by the requirement.

Worked example: the exact threshold

Requirement: output BONUS when a player's score is 100 or more; otherwise output NO BONUS.

01 INPUT score
02 IF score > 100 THEN
03     OUTPUT "BONUS"
04 ELSE
05     OUTPUT "NO BONUS"
06 END IF

The expected column comes from the requirement. The predicted column comes from tracing the supplied algorithm; it is not a claim that the code was run.

The algorithm is not fit for purpose because the permitted input 100 produces the wrong result. The two passing cases do not cancel that failure. Passing tests provide evidence of fitness, but one passing test does not prove that every permitted input will work.

Use the exact endpoints in the following check.

Comparisons and loop passes

Once an algorithm has evidence of fitness, its efficiency can be evaluated. Efficiency concerns the resources used to complete the task. Two useful indicators of work are comparisons and loop passes.

A loop can repeat a comparison, but the two counts measure different aspects of the work.

The comparison being counted must be named. For example, a question might count only comparisons between a list item and a target, or it might ask for every evaluated condition. Use the same definition for both algorithms. Under otherwise comparable conditions, fewer executed comparisons or loop passes usually means less work and therefore a shorter execution time, but the counts do not give an exact time on every computer.

Worked example: stopping when the target is found

Both written algorithms use this explicit input:

data = [14, 7, 22, 9, 5]
target = 7

Algorithm A: inspect every item

01 found = False
02 for value in data:
03     if value == target:
04         found = True
05 print(found)

Algorithm B: stop after a match

01 found = False
02 position = 0
03 while position < len(data) and found == False:
04     if data[position] == target:
05         found = True
06     position = position + 1
07 print(found)

For a fair comparison here, count only the item-to-target comparison on line 3 of Algorithm A and line 4 of Algorithm B. Count each execution of the main loop body as one pass.

Both algorithms meet the requirement for this input, but Algorithm B is more efficient by these two measures: it makes three fewer target comparisons and three fewer loop passes. If the target were absent, both would inspect all five items, so the size and position of the input matter to the evaluation.

Comparisons and passes are not interchangeable. Suppose Algorithm C uses one loop over six readings and makes two data comparisons in each pass. It makes 6 x 2 = 12 data comparisons in 6 passes. Algorithm D uses two consecutive loops over the same six readings, making one data comparison in each pass. It also makes 6 + 6 = 12 data comparisons, but it takes 12 loop passes.

Apply both counts to a fresh pair of algorithms.

Memory use

An algorithm needs memory for the data it holds while it runs. This can include input data, output data, variables, temporary values and extra arrays or other collections.

For a fair comparison, state the basis. If both algorithms receive the same input list, compare their additional memory: storage created beyond that shared input. Do not judge memory from source-code length or simply count variable names. One list containing 10,000 values can require much more storage than several variables that each hold one value.

Worked example: reverse 1,000 readings

Requirement: reverse a list of 1,000 readings. The original order does not need to be preserved.

Both methods can produce the required reversed order. Algorithm S is more memory-efficient because its additional storage does not include another 1,000-item list. An exact number of bytes cannot be calculated unless the storage size of each item and control variable is supplied.

The requirement matters. If it instead said that the original list must remain unchanged, Algorithm S as described would not be fit for purpose. A memory-saving choice cannot override a mandatory requirement.

Use that additional-memory basis in the following comparison.

Evaluate in context

A complete evaluation does more than attach the label efficient. It uses evidence and makes the decision criteria visible:

1. State the functional and resource requirements.
2. Use test data to compare expected and predicted results.
3. Reject or qualify an algorithm that fails a mandatory requirement.
4. For suitable algorithms, compare counts from the same inputs: comparisons, loop passes and additional memory.
5. Select an algorithm by linking its evidence to the priorities of the context.

Worked example: a handheld exhibit checker

A museum device checks whether an exhibit ID is in a list of 12 IDs. It must give the correct result when the ID is first, in the middle, last or absent. It may store at most five additional IDs. Response speed is useful, but the correctness and memory limits are mandatory.

The following counts come from consistent static traces of the two supplied algorithms:

River stores one additional ID; Bridge stores 12 additional IDs.

Both algorithms produce correct results for the supplied cases. Bridge uses fewer comparisons and passes for the middle, last and absent cases, although River uses fewer when the ID is first. However, Bridge exceeds the limit of five additional IDs, so it is not fit for this device. River should be selected because it meets the functional tests and memory requirement. If the memory limit were removed and repeated response speed became the main priority, the same evidence could justify Bridge instead.

There is therefore no context-free winner. A low count on one input is not proof of low counts on every input, and an efficient wrong answer is still wrong. For this GCSE evaluation, concrete counts and logical comparisons are enough; formal efficiency notation is not required.

Use the full evidence chain in the final check.