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.

Python Example

def maximum(values):
    best = values[0]
 
    for value in values[1:]:
        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.

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.

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.