Algorithms

Precise definition

An algorithm is a finite, unambiguous sequence of effective steps that transforms every permitted input into an output satisfying a stated specification. Correctness has two parts: partial correctness says that any terminating run returns a valid output; termination says that every permitted run eventually stops. Together they give total correctness.

Notation and mathematical language

Write an input instance as $x$, the algorithm as $A$, and its output as $A(x)$. A precondition $P(x)$ describes legal inputs and a postcondition $Q(x,A(x))$ describes required outputs. For a loop, an invariant $I$ is true before and after every iteration; a decreasing non-negative variant can establish termination.

Conceptual picture

An algorithm is not merely code in a particular language. It is the mathematical process behind the code. A trace table records the state after each step, while an invariant captures what all those states have in common. Correctness explains why every input works; testing can only reveal behaviour on selected inputs.

Conditions and key results

A correctness argument must cover the declared input domain, including empty and boundary instances. A loop-invariant proof establishes initialization, maintenance, and termination. Efficiency is then analysed under an explicit cost model and input-size measure; a fast algorithm that violates its postcondition is still wrong.

A reliable strategy

1. State the input, output, precondition, and postcondition before choosing operations.
2. Trace a small ordinary case and at least one boundary case to expose state changes.
3. Identify an invariant and prove initialization and maintenance; identify progress toward termination.
4. After correctness, count dominant operations as a function of input size and report the appropriate asymptotic bound.

Fully worked example

Interpretation and application

Algorithms govern routing, scheduling, searching, encryption, and numerical computation. In practice, input validation belongs to the specification: if negative values, missing data, or overflow are possible, either the precondition must exclude them or the algorithm must define how they are handled.

Common mistakes

Verification and reasonableness

• Trace the algorithm on the smallest legal input and verify the postcondition directly.
• Check that the proposed invariant holds before the loop and survives every possible iteration.
• Use the termination condition together with the invariant; neither statement alone usually proves the postcondition.

Practice

1. For the worked algorithm with $a=2$ and $b=5$, what values does $m$ take?
2. Why does $b-m$ prove termination?
3. Can testing 1,000 inputs prove total correctness over all integers?

Further deduction

A second correctness pattern is linear search. After examining the first $i$ entries, an invariant can state that none of positions $0$ through $i-1$ contains the target. If entry $i$ is not the target, advancing $i$ preserves that claim; if the target is found, its index satisfies the postcondition. If $i$ reaches the array length, the invariant proves the target is absent. The same invariant supports two legitimate return paths, and the index increases toward a finite bound, so termination is explicit rather than assumed.

Related topics

• Big O Notation
• Methods of Proof
• Mathematical Induction