Correctness

Correctness means that an algorithm produces the intended result for every valid input. An algorithm is not good enough merely because it is fast on examples.

Correctness asks why the steps lead to the right answer.

Core Idea

To reason about correctness, first state what the algorithm is supposed to produce. Then explain why each part of the algorithm preserves or moves toward that goal.

For simple algorithms, examples may build confidence, but examples are not a proof. A few passing cases do not show that every valid input works.

Correctness usually depends on an input contract. The contract says which inputs are valid and what output is expected. If the contract is vague, the algorithm can appear correct in one interpretation and wrong in another.

Function Contract

maximum(values) expects a non-empty sequence of comparable values. Comparable means the values can be ordered with >.

It returns one value from the sequence whose value is at least as large as every other value in the sequence. The function is not defined for an empty input because there is no maximum element to return.

Python Example

def maximum(values):
    best = values[0]
 
    for index in range(1, len(values)):
        value = values[index]
        if value > best:
            best = value
 
    return best

The correctness argument is that after each loop iteration, best is the largest value among the elements seen so far. When the loop ends, all elements have been seen, so best is the largest value in the whole list.

A Correctness Argument

For maximum, the claim can be broken into three parts.

Before the loop starts, best is values[0], so it is the largest value among the first element seen so far.

During each loop iteration, the algorithm compares the next value with best. If the new value is larger, best becomes that value. Otherwise best stays the largest seen value.

After the loop ends, every element has been seen. Since best is the largest among all seen elements, it is the maximum of the whole list.

This reasoning is stronger than testing with [3, 8, 2], because it explains why any non-empty list works.

Edge Cases

Correctness often fails at boundaries:

• Empty input.
• One-element input.
• Duplicate values.
• Negative values.
• Already sorted or reverse-sorted data.
• Disconnected graphs.
• Cycles.

The example function assumes a non-empty list. If empty input is allowed, this implementation is incomplete because values[0] would fail.

Common Confusions

Testing and correctness are related, but they are not identical. Tests can reveal mistakes and document expected behavior. They do not, by themselves, prove that the algorithm works for all inputs.

Correctness also depends on the input contract. The example above assumes values is non-empty. If empty input is valid, the algorithm needs a different behavior.

Another common confusion is treating “works on the sample” as correctness. Sample tests usually cover only a few cases. They are useful checks, not a complete explanation.

When To Use It

Use correctness reasoning whenever a solution is more than a direct library call. It is especially important for loops, recursion, greedy choices, graph traversal, and dynamic programming transitions.

When studying an algorithm, ask two questions separately: why does it produce the right answer, and how much time and memory does it use? Both matter.

The Main Point

Correctness means the algorithm returns the required answer for every valid input, not only for examples. State the input contract and the reason the maintained facts imply the final result.