Algorithms from zero
Is the algorithm correct?
You test your function on [3, 9, 2, 7] and it returns 9 — correct. You test it on [1, 2, 3] and it returns 3 — correct. You feel confident. Then in production, it crashes on an empty list. Or it returns the wrong answer on all-negative numbers. Testing a few examples is not the same as being sure your algorithm is correct for every possible input.
After this lesson you can define what correctness means for an algorithm, spot bugs by considering edge cases, and use a loop invariant to reason that a loop solves its problem correctly.
An algorithm is correct if it produces the right output for every valid input, not just the ones you tried. This definition requires two things:
- A specification — a precise statement of what output is expected for what input. For example: “Given a list of numbers, return the largest one.”
- Proof — a logical argument that the algorithm meets the specification for all possible inputs.
Testing is not proof. Testing can reveal bugs, but it cannot prove correctness, because you cannot test every possible input. Edge cases — unusual or boundary inputs like empty lists, single elements, or all-equal values — are where bugs hide.
The tool to prove a loop is correct is called a loop invariant: a statement about the loop that is true before it runs, remains true after each iteration, and is useful when the loop finishes.
Consider the largestOf function from lesson 01:
1
function largestOf(numbers) {
2
let largest = numbers[0];
3
for (let i = 1; i < numbers.length; i++) {
4
if (numbers[i] > largest) {
5
largest = numbers[i];
6
}
7
}
8
return largest;
9
}
- L2 After this line, largest = numbers[0]
- L3 Loop: we will update largest as we see more numbers
- L8 Loop invariant: after processing numbers[0..i], largest holds the max
The loop invariant is: “After processing the first i+1 numbers (from index 0 to i), largest holds the largest of those numbers.”
- Before the loop: We set
largest = numbers[0], so the invariant is true for i=0. - Each iteration: We compare
numbers[i]tolargest. If it is bigger, we updatelargest. Either way, after the iteration,largestis still the largest of the numbers we have seen so far. - After the loop: The loop exits when
i = numbers.length. By the invariant,largestis the largest of all numbers. This is what we promised to return.
This logical argument proves the algorithm is correct — not by testing, but by reasoning.
Let us write the largestOf function and then reason about its correctness:
function largestOf(numbers) {
let largest = numbers[0];
for (let i = 1; i < numbers.length; i++) {
if (numbers[i] > largest) {
largest = numbers[i];
}
}
return largest;
}Try it on a few inputs:
All these examples pass. But you might be tempted to say “I tested it, so it is correct.” That is a trap. The loop invariant is what makes you sure.
Let us trace the algorithm on [-5, -1, -10] to see the loop invariant in action:
1
function largestOf(numbers) {
2
let largest = numbers[0];
3
for (let i = 1; i < numbers.length; i++) {
4
if (numbers[i] > largest) {
5
largest = numbers[i];
6
}
7
}
8
return largest;
9
}
The invariant stays true every step. This gives us certainty, not just for this example, but for every valid input.
Proving correctness has no direct cost in terms of steps — it is a logical argument, not computation. But understanding the structure of the algorithm (the loop invariant) often makes the code faster or clearer. For now, the key insight: a correct algorithm is one you can reason about with an invariant.
What is a loop invariant?
Why is testing alone not enough to prove an algorithm is correct?
If a loop processes elements from index 0 to n-1, and the invariant is 'largest holds the max of elements [0..i]', what is the invariant when the loop finishes and i = n?
An algorithm fails on negative numbers even though it works on positive ones. What is this an example of?
Arrange the steps to prove a loop is correct using a loop invariant:
- Prove the invariant is true before the loop (initialization)
- Prove the invariant remains true after each iteration (maintenance)
- Show that when the loop exits, the invariant tells us the answer is correct (termination)
- State what the loop invariant is
Edge cases
Edge case: empty list. The function crashes on an empty list because numbers[0] does not exist. A correct version would check if (numbers.length === 0) first. The specification must say what to return for empty input — perhaps null, or throw an error. Without that specification, you cannot say if the function is correct.
Common mistake
A buggy variant. What if we initialize largest = 0 instead of largest = numbers[0]?
function largestOf_WRONG(numbers) {
let largest = 0; // BUG: should be numbers[0]
for (let i = 0; i < numbers.length; i++) {
if (numbers[i] > largest) {
largest = numbers[i];
}
}
return largest;
}Test: largestOf_WRONG([-5, -3, -1]) returns 0, not -1. This fails on all-negative lists. The loop invariant would have caught this: if we initialize largest = 0, the invariant “largest holds the max of [0..i]” is false before the loop even starts, because the maximum of [-5] is -5, not 0. A faulty invariant means a faulty algorithm.
A friend tests an algorithm on 100 random inputs and it passes all of them. Does this prove the algorithm is correct?
An algorithm is correct if it produces the right output for every valid input. This is defined by a specification — what output is expected for what input. Testing can reveal bugs but cannot prove correctness because you cannot test every input. Edge cases — unusual or boundary inputs — are where bugs hide.
A loop invariant is a statement about a loop that is true before it runs, stays true after each iteration, and helps you prove the loop is correct. By proving three things (initialization, maintenance, termination), you can be certain the loop works for all inputs. This is a logical proof, not just confidence from testing.