In computer science, correctness is the extent to which an algorithm will halt (i.e., it finishes computations in finite time) and outputs the correct solution for every input.
We can prove correctness with:
- Basic proof techniques, like counterexample, contraposition, or contradiction
- These are helpful if the algorithm doesn’t use loops or recursion.
- Induction
- Loop invariant or weak induction, for iterative algorithms
- Especially for loop based algorithms (i.e., where they make up the bulk of the loop), loop invariants are good methods.
- Strong induction, for recursive algorithms
- Loop invariant or weak induction, for iterative algorithms