Essential properties

1. Input: The values needed by the algorithm must be clearly stated. Some algorithms may need no external input.
2. Output: The result to be produced must be clearly stated.
3. Definiteness: Every step must be clear. A person following it should not have to guess what to do.
4. Finiteness: The algorithm must finish after a finite number of steps for every allowed input.
5. Effectiveness: Each step must be simple enough to carry out using the available operations.

Example: largest of three numbers

Read a, b and c. Set maximum = a. If b is larger than maximum, replace maximum with b. Then compare c with maximum and replace it if needed. Display maximum. For 4, 9 and 2, the result is 9. Each step has a clear action, and the algorithm finishes after two comparisons.

Correctness

An algorithm must give the required result for every allowed input. Check negative numbers and equal values as well as an ordinary example. An algorithm can have clear steps and still use a wrong formula, so clarity alone does not prove correctness.

Time and space complexity

Time complexity describes how the number of operations grows as the input size grows. Space complexity describes the memory needed. Big O is used to describe an upper growth limit. Comparing exactly three numbers takes constant work, O(1). Checking n values one by one takes O(n) time. The best case is the input of a given size that needs the least work; the worst case needs the most work.

Reference table

Key points

• State the permitted input domain.
• Finiteness is about termination, not about a particular programming language.