# Correctness

Information on this page is taken from *The Algorithm Design Manual* by Steven
S. Skiena.

Reasonable-looking algorithms can easily be incorrect. Algorithm correctness is
a property that must be carefully demonstrated. The primary tool to distinguish
correct algorithms from incorrect ones is a **proof**. A proof has four main
parts.

- Clear, precise statement of what you are trying to prove.
- Set of assumptions.
- Chain of reasoning that takes you from the assumptions to the statement you are trying to prove.
- Little, black square or
*QED*.

Computer scientists usually prove things with **proof by induction** or **proof
by contradiction**. We'll see induction below.

To reason about an algorithm, you need a careful description of the sequence of steps to be performed. The three most common forms of algorithmic notation are English, pseudocode, or a real programming language. These methods have natural tradeoffs between expression and precision.

## Incorrectness

The best way to prove that an algorithm is *incorrect* is to produce an
instance in which it yields an incorrect answer. Such instances are called
**counter-examples**. Good counter-examples are verifiable and simple. Many
tricks exist for finding counter-examples.

*Think small*: small examples are easier to reason about.*Think exhaustively*: consider different types of examples.*Go for a tie*: try similar values in the input collection.*Seek extremes*: e.g. use values that are far apart or close together.

## Induction

**Mathematical induction** is a common choice for proving correctness. If
you're familiar with recursion, you're familiar with induction; recursion
*is* induction. In both, we have general and boundary conditions. The
general condition breaks the problem into smaller and smaller pieces and the
boundary condition terminates the recursion. Suppose that you are trying to
prove that a statement holds true for all natural numbers (all
\(n\)). Induction would usually take the form:

- Show that the statement holds for the base case (usually \(P(0)\) or \(P(1)\)).
- Assume that \(P(k)\) is true.
- Prove that the statement also holds for \(P(k + 1)\).