algorithm A prescribed set of well-defined rules or instructions for the solution of a problem, such as the performance of a calculation, in a finite number of steps. Expressing an algorithm in a formal notation is one of the main parts of a
program; much that is said about programs applies to algorithms, and vice versa. An
effective algorithm is one that is effectively computable (see
effective computability). The study of whether effective algorithms exist to compute particular quantities forms the basis of the theory of algorithms.
Save for the simplest of algorithms it is difficult to
prove that an algorithm is correct (see
program correctness proof), or even to specify the effect it is intended to achieve. In practice it is usually necessary to be content with
algorithm validation. This process certifies, or verifies, that an algorithm will perform the calculation required of it. It involves testing the routine against a variety of instances of the problem and ensuring that it performs satisfactorily for these test cases. If the test set is chosen sufficiently well there can then be confidence in the algorithm.
Algorithm analysis is the study of the performance characteristics of a given algorithm. One branch of this study,
average-case analysis, examines the average behavior of the algorithm.
Worst-case analysis studies the behavior when all circumstances are as unfavorable as possible. Algorithms can be analyzed in terms of their
complexity and efficiency, where
algorithm efficiency is characterized by its
order.
