Verifying and comparing algorithms

Software for banking, medicine or space must work correctly in every situation, so algorithms must be verified. One way is to check a formula with a small case: the sum 1 + 2 + … + N should equal N(N + 1)/2. Try N = 4: 1 + 2 + 3 + 4 = 10, and 4 × 5 ÷ 2 = 10. It works.

A dry run means taking some input values and going through every step of the algorithm by hand, writing down what happens. It finds wrong steps and missing details. Test with many kinds of input, especially tricky ones, not just easy ones.

An example: an algorithm adds two lengths of time by adding the hours and the minutes separately. For 3 h 45 min + 1 h 30 min, it gives 4 h 75 min, which is wrong. The dry run shows a missing step: IF the minutes total is 60 or more, THEN add 1 to the hours and subtract 60 from the minutes. Now the answer is 5 h 15 min.

Often there are several algorithms for the same problem. To check whether a number is prime, we could:

• divide it by every number smaller than it;
• divide only by numbers up to half of it;
• divide only by numbers up to its square root (the fewest divisions);
• divide only by numbers in a stored list of primes (fewer calculations, but extra memory to keep the list).

Algorithms are compared by the processing time they need (time complexity) and the memory they use (space complexity).