How Do You Prove an Algorithm Is Correct?

To prove an algorithm is correct, you show two things: it gives the right output for every valid input, and it stops after a finite number of steps. That sounds simple, but the proof has to match the code line by line. Testing cannot do that job. A test might cover 50 cases or 5,000 cases, but it still misses the ones you did not try. A proof covers the whole input set, including edge cases like an empty array, a 1-item list, or a search key that never appears. In a data structure and algorithms course, professors care about this because correctness tells you more than speed. An algorithm can run in 1 millisecond and still return the wrong answer. Interviewers ask the same thing in a sharper way: why does this method work, and why does it stop? If you can explain preconditions, postconditions, loop invariants, and induction, you can defend your answer instead of hand-waving. The core idea is plain. State what must be true before the algorithm starts. State what must be true when it ends. Then prove that each step preserves the truth until the last step finishes the job. That is the real logic behind algorithm correctness, and it matters in both class work and technical interviews.

Why Does Algorithm Correctness Need Proof?

Algorithm correctness needs proof because a few passing tests never cover every valid input, while a proof covers the full set, from 0-length arrays to 10,000-item lists. In plain terms, you show that the code matches its specification, returns the right output, and stops.

That last part matters. A sorting routine that outputs a sorted list after 2 hours on a 5-item input still fails as a correct algorithm in any serious sense. Correctness has two sides: partial correctness, which means the output is right if the program ends, and termination, which means the program actually ends.

Testing and proof solve different problems. Testing asks, “Did it work on these 12 cases?” Proof asks, “Will it work on all cases that meet the precondition?” In a data structure and algorithms course, that difference shows up fast, because professors expect students to justify binary search, merge sort, and graph traversals with logic, not vibes.

The catch: A proof does not depend on luck or sample size, and that makes it stronger than even 1,000 clean test runs. Interviews use that same standard when they ask you to explain why your method works, not just what it does.

One honest downside: proofs take time, and a clean proof can take 20 minutes longer than writing code. Still, that extra time pays off because it exposes hidden bugs like off-by-one errors, missing base cases, and loops that never move their pointers.

The logical methods for proving that an algorithm works correctly also help you reason about performance, because termination arguments often reveal how many steps a loop can take. That kind of thinking looks sharp in class and in whiteboard interviews.

What Are Preconditions and Postconditions?

A good proof starts with a precise contract: the precondition says what must already be true before the code runs, and the postcondition says what the code guarantees afterward. If you write that contract badly, even a 3-line algorithm can become impossible to prove.

• Precondition: the input array has length n ≥ 1, and n is known before the loop starts.
• Postcondition: the returned value equals the smallest element in positions 0 through n-1.
• Precondition: the list is sorted in nondecreasing order, which makes binary search valid on every step.
• Postcondition: if the target appears, the algorithm returns an index i with 0 ≤ i < n; if not, it returns -1.
• Good wording names the exact range. Saying “the data is valid” tells you almost nothing, but saying “0 ≤ i < 50” gives you something you can prove.
• Reality check: Vague promises like “works fast” or “gives the right answer” do not count, because they leave out 1 huge thing: the input limits.
• Common mistake: writing the postcondition as if the answer already exists, such as “the array is sorted,” before the algorithm has done any work.

A strong precondition/postcondition pair often looks boring, and that boringness is a good sign. It strips out guesswork. In a proof for insertion sort, you might say the precondition allows any array of length 0 or more, and the postcondition says the same array comes back sorted.

Missing edge cases wreck proofs fast. If you forget the empty list, you miss one of the first questions a professor or interviewer will ask.

How Do Loop Invariants Prove Correctness?

A loop invariant is a statement that stays true before the loop starts, after every pass, and right before the loop ends. That one idea powers many proofs in data structure and algorithms work, from linear search to insertion sort.

Take linear search over 8 items. A useful invariant says: before each test of position j, every item before j has already been checked and none matched the target. That sounds small, but it does a lot. It proves the algorithm never skips a possible match, and it also shows why the answer is correct when the loop stops.

Here is the structure. First, you prove initialization: before the first pass, the statement is true because no items have been checked yet. Then you prove maintenance: if it holds at position j, it still holds at position j + 1 after one more comparison. Finally, you prove termination: when j reaches n, the loop ends, so every item has been checked. That gives you partial correctness. Add a termination argument, like “j increases by 1 and n stays fixed,” and you get total correctness.

What this means: The invariant does not describe the whole algorithm; it describes the part that must stay steady while the loop moves. That difference matters a lot, and I think students miss it more than any other proof idea.

A weak invariant says too little, like “the loop is making progress.” A strong one says enough to pin down the answer, like “the prefix of length j already contains the smallest j elements” in insertion sort. The stronger version can feel fussy, but it gives you something you can actually use.

The downside is that invariants can feel unnatural at first. After 2 or 3 practice problems, though, they start to feel like a flashlight for the code.

How Does Mathematical Induction Prove Algorithms?

Mathematical induction proves algorithms that repeat smaller versions of the same problem, especially recursive routines and divide-and-conquer code. You use it when the algorithm on size n depends on size n-1, n/2, or another smaller input.

1. State the claim clearly for every input size, such as “merge sort returns a sorted array of length n.” The claim has to match the code, not a vague idea of what you hope it does.
2. Prove the base case, usually n = 0 or n = 1. For recursion, this is the 1-step case that stops the chain, and without it the proof has nowhere to land.
3. Assume the claim holds for smaller inputs. That induction hypothesis is the engine of the proof, and it often covers size n - 1 or two subproblems of size n/2.
4. Use that assumption to prove the step for size n. In merge sort, if each half of length n/2 comes back sorted, the merge step gives a sorted array of length n in about O(n) work.
5. Close the proof by saying the claim now holds for all n in the chosen range, such as every n ≥ 1. That final line matters because it turns a local argument into a full one.

Induction feels natural for recursive array processing and trees because the data itself has a smaller copy inside it. A binary tree with 7 nodes has subtrees with fewer nodes, so the proof mirrors the structure.

Bottom line: If the code breaks a problem into 2 smaller parts, induction usually fits better than a loop invariant. That is not a rule, just the pattern I trust most.

The limitation is simple: induction can get messy when the algorithm changes shape midstream, like when a loop and recursion mix. Even then, the same logic still appears, just in a rougher jacket.

Which Proof Mistakes Break Algorithm Correctness?

Most proof mistakes come from proving the wrong thing, skipping edge cases, or using a statement that sounds smart but does not actually connect to the code. A proof that misses 1 boundary case can collapse on the first exam question.

• Testing 5 examples does not prove anything about all inputs, even if every example passes.
• Termination and correctness are different. A loop can stop after 100 steps and still return the wrong index.
• Weak invariants say too little, so they never reach the final answer. Strong ones can say too much and become false after 1 update.
• Ignoring n = 0, n = 1, or an empty list usually leaves a hole that shows up fast in class or interviews.
• Do not prove a result that no one asked for. If the postcondition says “returns the minimum,” proving “returns a value from the array” misses the target entirely.
• Worth knowing: A proof that never names the precondition and postcondition has no anchor, so it drifts away from the actual algorithm.
• One bad habit: writing “obvious” instead of showing the 2 or 3 steps that make the logic work.

I have seen students lose points on a 20-point proof because they skipped the exact stopping rule. That hurts, because the fix usually takes only 1 extra sentence.

The best habit is blunt honesty. If your claim does not mention the input limits, the loop state, and the final output, the proof still has a gap.

How Do You Write a Full Correctness Proof?

A full proof uses one simple chain: specification, precondition, core proof, termination, and conclusion. You start by naming what the algorithm must do, then you write the assumptions it needs, and then you prove the steps that connect the start to the finish.

For a loop-based algorithm, write the invariant, prove it starts true, prove it survives each pass, and prove it gives the postcondition when the loop ends. For a recursive algorithm, write the claim, prove the base case, use induction or a smaller subproblem, and then show the result follows for size n. That structure works for arrays of length 10 and trees with 1,000 nodes.

A reusable checklist helps in a data structure and algorithms course or in a study online plan for transferable credit: 1) state the input limits, 2) state the output rule, 3) name the invariant or induction claim, 4) show why the loop or recursion stops, and 5) connect the end state to the postcondition. If any one of those five steps goes missing, the proof wobbles.

The catch: The proof must match the code you actually wrote, not the version you wished you wrote. A clean-looking proof for the wrong algorithm still fails.

This is where careful reading pays off. A professor can spot a gap in 30 seconds, and an interviewer can too. Once you learn to write proofs this way, you stop treating correctness like a mystery and start treating it like a checklist you can defend under pressure.

Frequently Asked Questions about Algorithm Correctness

Final Thoughts on Algorithm Correctness

Algorithm correctness looks abstract until you break it into parts. Then it gets plain. You write what must be true before the code runs, what must be true when it ends, and what must stay true in the middle. That three-part shape covers most proofs you will meet in class. Preconditions and postconditions give you the contract. Loop invariants handle repetition. Induction handles recursion and divide-and-conquer. Termination keeps the whole proof honest, because a correct answer that never arrives still fails the assignment and the interview question. The best students do not treat proofs like magic words. They treat them like receipts. Each sentence has a job, and each job has to line up with the code. That habit pays off in a data structure and algorithms course, on whiteboards, and in any setting where someone asks you to justify your method in 2 minutes. Start with one simple algorithm, like linear search or summing an array of 5 numbers. Write the contract. Write the invariant or induction claim. Then check the stopping point. Once you can do that cleanly, harder proofs stop feeling random and start feeling readable.