What an Algorithm Is — Correctness and Termination

Hook #

You've written code that ran without errors and produced the wrong answer. Every working engineer has. The compiler can verify that your syntax is legal; it cannot verify that your sorted list is actually sorted, or that your loop terminates on every input. That second kind of verification is what this course is about — and the first step is being precise about what it means for an algorithm to be correct in the first place.

What you'll be able to do by the end of this lesson #

• State, in one sentence, what makes a procedure an "algorithm" rather than just "some code."
• Distinguish between partial correctness (if it terminates, the answer is right) and total correctness (it terminates and the answer is right) — and explain why both matter.
• Give a one-line argument for why a simple iterative procedure terminates, citing the loop variant that decreases on each iteration.
• Recognise three classic ways an algorithm can be subtly wrong: an off-by-one, a missing base case, and an unhandled input.

A quick try before we start #

Before reading further: in your own words, what makes a piece of code an algorithm — and what makes one merely a "script that happened to work"? Hold your answer; we'll come back to it.

Why this matters here #

This is the foundation course for everything algorithmic that follows. Before we measure how fast an algorithm is (the next lesson), we have to agree on what it means for it to work at all. A sort that's blazingly fast and sometimes returns unsorted output is worse than a slow sort that's always right.

The framing matters for a second reason: the rest of the path treats algorithms as objects of analysis. We won't just write them; we'll prove properties about them — that they terminate, that they produce the right output, that they use a bounded amount of memory. The proof techniques you spent last course building (induction, contradiction, contrapositive) are about to start paying rent.

The engineer's lens #

An algorithm is the what of a procedure; an implementation is the how. Same algorithm, two languages: same correctness properties. This is why CLRS uses pseudocode — the algorithm exists above the language. When a Ruby quicksort and a C quicksort give the same answer for the same input but the C one runs in 1ms and the Ruby one in 50ms, they share an algorithm and differ only in implementation. We'll measure the algorithm; we'll benchmark the implementation. Different questions.

Termination is the property that working engineers forget exists until they ship code that hangs. The simplest discipline that catches most bugs: for every loop you write, name out loud the quantity that strictly decreases on each iteration and the floor it can't go below. If you can't, the loop might not terminate. (Recursion gets the same treatment, with the recursive call as the "iteration" and the argument-towards-base-case as the quantity that decreases.)

What to focus on in MIT 6.006 Lecture 1 #

• The first 15 minutes — what an algorithm is, why we care about asymptotic behaviour rather than wall-clock time. Watch carefully.
• The middle section on the peak-finding problem — this is the first running example of the course. Notice how Demaine moves from a naive O(n) version to a clever O(log n) version. The structure of the argument (loop invariant + termination) is what matters; you'll reuse it.
• Skip or skim the model-of-computation digression near the end on first watch. It matters later in the course; not load-bearing for this lesson.

Explain it back #

In your own words, as if explaining to a colleague who's seen the concept but not used it: pick a small loop from any project you've written — a search loop, a parsing loop, a retry loop. In two or three sentences, write out: (a) the quantity that decreases on each iteration, (b) the floor it can't go below, (c) why the loop is therefore guaranteed to terminate. Bring this to your next Bodhi session.

Where this connects #

Backward: Mathematical induction from Discrete Math — the technique you'll use to prove a loop invariant holds across iterations is induction on the iteration count. The base case is "the invariant holds before the loop starts"; the inductive step is "if it held going into iteration k, it holds going out."

Forward: Every algorithm in this course will be analysed for correctness and termination first, complexity second. When we hit recurrences in lesson 4, the termination argument becomes the well-foundedness argument: the recursive call's argument is strictly closer to the base case.