Overview
Algorithm correctness is the property that a procedure produces the result required by its specification for every valid input. An algorithm is not correct merely because it works on a few test cases. Its logic must be valid for the entire permitted input domain.
Specification
A specification defines what an algorithm is expected to do. It describes the permitted inputs, required outputs, assumptions, and relevant behavior. Correctness is evaluated by comparing the algorithm's actual behavior with this specification.
Partial Correctness
An algorithm is partially correct if, whenever it terminates after receiving a valid input, the result satisfies the required postcondition. Partial correctness alone does not guarantee that the algorithm terminates.
Termination
Termination means that the algorithm eventually completes. To establish total correctness for a terminating algorithm, it is necessary to establish both partial correctness and termination for every permitted input.
Preconditions
A precondition is a condition that must be true before an algorithm begins. For example, a binary search algorithm generally requires its input sequence to be sorted.
Postconditions
A postcondition is a condition that must be true after the algorithm completes successfully. For binary search, the postcondition states that the target is returned if it exists, or that its absence is correctly reported.
Hoare Logic
Hoare logic is a formal system for reasoning about program correctness. A Hoare triple has the form {P} C {Q}, where P is the precondition, C is a program or command, and Q is the postcondition. It expresses that if P holds and C terminates, then Q holds.
Loop Invariants
A loop invariant is a property that remains true before and after each iteration of a loop. It is used to reason about the correctness of iterative algorithms. A standard proof establishes initialization, maintenance, and termination.
Initialization
The initialization step proves that the invariant is true before the first loop iteration.
Maintenance
The maintenance step proves that if the invariant is true before an iteration, it remains true after that iteration.
Termination Proof
The termination step shows that the loop eventually ends and that the invariant, together with the termination condition, implies the desired postcondition.
Inductive Proof
Many algorithm correctness proofs use mathematical induction. The proof establishes a base case and then demonstrates that the property remains true when moving from one problem size to the next.
Testing Vs Proof
Testing checks an algorithm on selected inputs and is valuable for discovering defects. However, testing a finite collection of cases cannot generally prove correctness for an unlimited input domain. Formal proof provides a logical argument covering all inputs within the specification.