In his book The Art of Computer Programming, Volume 1: Fundamental Algorithms, Donald E. Knuth asserts that an algorithm must satisfy the following five properties:
- Input: The algorithm must have input values from a specified set.
- Output: The algorithm must produce the output values from a specified set of input values. The output values are the solution to a problem.
- Finiteness: For any input, the algorithm must terminate after a finite number of steps.
- Definiteness: All steps of the algorithm must be precisely defined. Every instruction within the algorithm should be clear and unambiguous. An algorithm must explicitly describe how the computation is to be carried out. The property of definiteness ensures that the agent executing the instructions will always know which command to perform next. Some examples of algorithms that do not satisfy the property of definiteness are:
- an algorithm that involves dividing a number by zero without any checks or safeguards. Dividing by zero is mathematically undefined, and an algorithm that doesn’t handle this scenario can lead to unexpected results or errors in the computation.
- an algorithm that attempts to calculate the square root of a negative number without accounting for complex numbers. The square root of a negative number is not a real number but a complex one. If the algorithm doesn’t handle this properly, it might produce invalid or nonsensical results.
- Effectiveness: It refers to the ability of an algorithm to consistently and accurately produce a meaningful and correct result for all possible valid inputs (including edge cases) within a finite amount of time. The steps of the algorithm must be basic enough so that, for example, someone using a pencil and paper could carry them out exactly.