What Is an Algorithm?

You have already met dozens of algorithms without being told that's what they were. Merge sort, quicksort, binary search, linear search, breadth-first search; even the rote procedures for multiplying ($374\times 285$) or adding ($724+1366$) two integers by hand; even tidying a room by a fixed set of rules. What unites them is captured by a simple working definition:

def fib(n: int) -> int:
  if n <= 1:
    return n
  return fib(n-1) + fib(n-2)

def fib2(n: int) -> int:
  M = [0, 1]
  for i in range(1, n):
    M.append(M[-1] + M[-2])
  return M[-1]

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

fib2 :: Int -> Int
fib2 n
  | n <= 1    = n
  | otherwise = fib2 (n - 1) + fib2 (n - 2)

That definition is deliberately blunt. Erickson sharpens it the same way: an algorithm is a procedure a rock could follow, where every step is so mechanical that no intelligence, intuition, or luck is required to carry it out.¹ CLRS frames it operationally: a well-defined computational procedure that takes a value (or set of values) as input and produces a value as output.² Skiena adds the engineer's caveat: it must work correctly on every instance, not merely on the examples we happen to test.³

Three demands run through all of these, and through this entire course:

• Correctness. The algorithm produces the right output on every valid input. One counterexample is enough to sink it.
• Efficiency. It uses few resources (time, space) as the input grows.
• Provability. We can argue, rather than assert, that the first two hold.

Communicating an algorithm

Having an algorithm in your head is not enough; you must convey it so that someone else can run it, trust it, and predict its cost. In this course every algorithm comes with four deliverables, and you should reach for all four by reflex:

1. High-level idea. One or two sentences of plain English.
2. Pseudocode. The steps, precise enough to analyze.
3. Proof of correctness. An argument that it always returns the right answer.
4. Complexity analysis. How its running time (and sometimes space) grows with the input.

These four are not independent checkboxes; they form a pipeline. The problem spec fixes what counts as a correct answer; the idea and pseudocode are two resolutions of the same method; the proof certifies the pseudocode against the spec; and the analysis measures that same pseudocode. Each deliverable feeds the next.

We will build a complete example of all four below. First, two preliminaries: what exactly the algorithm is for, and how we write it down.

Specifying the problem

Before writing an algorithm we must agree on the problem it solves: the set of legal inputs and, for each, the required output. A problem is a relation between inputs and outputs; an instance is one particular input. For sorting:

Notice what the specification hides: it says nothing about how to reorder the numbers, only what the result must satisfy. That separation of what from how is what algorithm design turns on.

Our running example will be a smaller, more concrete problem:

It is simple enough that you can see the whole algorithm at once, yet rich enough to demand all four deliverables, including a proof that is more subtle than it first looks.

Deliverable 1 — the high-level idea

Before any pseudocode, say what you intend to do in plain words. For $\text{Find-Max}$:

That sentence is the whole algorithm. Everything that follows makes it precise and proves it works.

Deliverable 2 — the pseudocode

We describe algorithms in pseudocode: precise enough to analyze, free of the syntactic noise of any real language. The high-level idea translates directly:

Two small but real design choices deserve attention. We seed $x$ with $A[1]$ rather than with $-\infty$ or $0$. This is why the specification insisted $n\ge 1$, so that $A[1]$ exists and the maximum is well defined. The loop starts at $i=2$, since $A[1]$ has already been accounted for by the seed.

As a second specimen of pseudocode, here is the classic insertion sort, which sorts $A[\mathrm{1..}n]$ in place by growing a sorted prefix one element at a time. We will return to it when we study sorting; for now it shows what nested loops and an in-place rearrangement look like on the page.

The outer loop walks a marker $j$ from left to right; everything before $j$ is already sorted. Each pass lifts $A[j]$ out as $key$, slides the larger sorted-prefix elements one slot right, and drops $key$ into the gap that opens up — exactly how you would tidy a hand of playing cards. The trace below shows the sorted prefix (shaded) absorbing one new element per row.

A picture of the idea

Here is $\text{Find-Max}$ mid-sweep on $A=⟨3,7,2,9,5⟩$. The cursor $i$ has just reached $A[4]=9$; everything to its left has been scanned, and $x$ holds the largest value among $A[\mathrm{1..3}]$. Since $A[4]>x$, the if fires and $x$ is updated to $9$.

The shaded cell is the element under the cursor; the region to its left (positions $1$ through $i-1$) is the part already summarized by $x$.

Deliverable 3 — proof of correctness

How do we know $\text{Find-Max}$ works? Erickson's a rock could run it intuition tells us the steps are mechanical, but it does not tell us the answer is right. Correctness needs an argument.

It is tempting to argue by contradiction (suppose $k$ is the true maximum but $\text{Find-Max}$ returns something else), but the clean way is to name what the loop preserves and induct on it. The key observation is that $x$ is only ever overwritten by a larger value, so $x$ never decreases and never holds anything that wasn't actually in the array. Made precise, that is a loop invariant: a statement true before and after every iteration.

We verify it with the three-part rubric that will recur throughout the course:

• Initialization. Before the first iteration $i=2$, so we must check $x=\max \left\{A[1]\right\}$. The seed line set $x\leftarrow A[1]$, and the maximum of a one-element set is that element. ✓
• Maintenance. Assume the invariant holds entering iteration $i$, i.e. $x=\max \left\{A[1],\dots ,A[i-1]\right\}$. The body sets $x\leftarrow \max \left\{x,A[i]\right\}$ (it overwrites $x$ exactly when $A[i]>x$, and leaves it otherwise). Hence after the body $x=\max \left\{A[1],\dots ,A[i-1],A[i]\right\}=\max \left\{A[1],\dots ,A[i]\right\}$, which is precisely the invariant for the next cursor value $i+1$. ✓
• Termination. The loop ends once the cursor would exceed $n$, i.e. with the invariant established for $i-1=n$. So $x=\max \left\{A[1],\dots ,A[n]\right\}$, and $\text{Find-Max}$ returns exactly the value the specification demands. ✓

Initialization, maintenance, termination: that triple drives correctness proofs, and we will use it constantly.

Aside: claims and the contrapositive

For algorithms that answer yes/no rather than compute a value, the same rigor takes a slightly different shape. Consider $\text{Linear-Search}(A,k)$, which reports whether key $k$ occurs in $A$. Correctness splits into two claims:

• Claim 1. If $k\in A$, then $\text{Linear-Search}$ returns found.
• Claim 2. If $k\notin A$, then $\text{Linear-Search}$ returns not found.

Claim 1 is direct: if $k$ sits at position $j$, the loop's $j$-th iteration tests $A[j]=k$ and returns found. Claim 2 is cleaner to prove in its contrapositive form. The logical identity is worth memorizing:

So instead of if $k\notin A$ then it returns not found, we prove the equivalent if it returns found then $k\in A$, which is immediate, since the only way to return found is to have just tested $A[j]=k$ for some $j$, witnessing $k\in A$. Choosing the easier of two logically identical statements is a recurring move in correctness proofs.

Deliverable 4 — complexity, in brief

The fourth deliverable asks how many steps the algorithm takes as a function of the input size $n$. For $\text{Find-Max}$, the seed and the final return cost a constant; the loop runs $n-1$ times, doing a comparison and at most one assignment each pass. If each line costs some machine-dependent constant $c_1,c_2,\dots$, the total is

a linear running time: double the array and you roughly double the work. The point of the $O(\cdot )$ is that it throws away the machine-specific constants and keeps only the growth rate.

That insertion sort, by contrast, is not always so cheap is exactly why fast needs care. On an array already in reverse order, every new element sifts past all its predecessors, costing $1+2+\cdots +(n-1)=\lfloor n(n-1)/2\rfloor$ comparisons, which is quadratic in $n$. On an already-sorted array it does only $n-1$ comparisons, which is linear: the same algorithm, wildly different costs.

Defining $O$, $\Omega$, and $\Theta$ precisely, and measuring this growth independently of the machine, is the subject of asymptotic analysis in the next lesson.

Takeaways

• An algorithm is a precise recipe of steps for solving a computational problem: a finite, mechanical, input-to-output procedure that must be correct on every instance.
• Every algorithm comes with four deliverables: high-level idea, pseudocode, proof of correctness, and complexity analysis. $\text{Find-Max}$ shows all four at full size.
• Specify the problem (legal inputs → required outputs) before the method. That is also what tells you to seed $x\leftarrow A[1]$ and require $n\ge 1$.
• Pseudocode is for humans to reason about; a loop invariant ($x$ only ever grows, to a value actually in the array) turns it looks right into a proof by initialization, maintenance, termination. Pin down which moment your invariant describes.
• For yes/no algorithms, prove each direction separately, and use the contrapositive $(p\Rightarrow q)\equiv (\neg q\Rightarrow \neg p)$ to pick the easier statement.
• Correctness and efficiency are separate questions: an algorithm can win one and lose the other.