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. A simple working definition unites them:

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.³

Pull those framings apart and you get a checklist. A procedure earns the name algorithm only if it is:

• Finite. It halts after finitely many steps on every valid input. Repeat until it looks sorted is not a step count you can bound.
• Definite. Every step is unambiguous: two executors starting from the same state and reading the same step do the same thing. Pick a good pivot fails this test until you say which element.
• Effective. Each step is basic enough to actually carry out: compare two numbers, copy a cell, add. Factor the integer is a legal step only if you already hold an algorithm for factoring.
• Anchored to a problem. It consumes specified inputs and produces specified outputs. A procedure that produces nothing computes nothing.

The multiplication procedure you learned as a child passes all four; season to taste fails definiteness, and a program that loops forever on one unlucky input fails finiteness. Three demands run through everything that does pass, 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:

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 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. Algorithm design rests on that separation of what from how.

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.

from typing import Sequence, TypeVar

from comparable import Comparable

Element = TypeVar("Element", bound=Comparable)

def find_max(array: Sequence[Element]) -> Element:
  """
    The maximum element of a non-empty `array`.\n
    Raises ValueError when `array` is empty, since the specification\n
    requires at least one element for "the maximum" to be defined.\n
  """
  if len(array) == 0:
    raise ValueError("find_max requires a non-empty array")

  # seed with the first element so the answer is always one of the inputs.
  largest: Element = array[0]

  # sweep the rest, keeping the larger of the running best and each element.
  for index in range(1, len(array)):
    largest = max(largest, array[index])

  return largest

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

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$.

from typing import TypeVar

from comparable import Comparable

Element = TypeVar("Element", bound=Comparable)

def insertion_sort(array: list[Element]) -> list[Element]:
  """
    Sort `array` into non-decreasing order in place, returning it.\n
    Stable: equal elements keep their original relative order, since the\n
    inner loop stops shifting as soon as it meets an element <= the key.\n
  """
  for marker in range(1, len(array)):
    key: Element = array[marker]

    # slide every sorted-prefix element greater than `key` one slot right.
    position: int = marker - 1
    while position >= 0 and array[position] > key:
      array[position + 1] = array[position]
      position -= 1

    # the gap that opened up is exactly where `key` belongs.
    array[position + 1] = key

  return array

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

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: $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.

The rubric on a harder loop: insertion sort

$\text{Find-Max}$'s invariant fit in one clause. Insertion sort (Algorithm 2) needs two, and the second is the one beginners drop:

The phrase "exactly the elements originally in $A[\mathrm{1..}j-1]$:q is doing real work.The prefix is sorted:q alone would not pin the algorithm down: a procedure could make the prefix sorted by destroying it (we will meet such asorter" shortly), so the invariant must also record that elements are only ever rearranged, never invented or lost. CLRS states the insertion-sort invariant in exactly this two-clause form.⁴

Before the proof, look at what one pass actually does to the array. Lifting $key$ out of its cell (line 2) leaves a hole; each pass of the while loop (lines 4–6) slides one prefix element right into the hole, moving the hole one step left; line 7 fills the final hole with $key$.

Now the three parts, argued against the line numbers of Algorithm 2.

• Initialization. Before the first iteration, $j=2$, so the prefix is the single cell $A[\mathrm{1..1}]$. Nothing has executed yet, so it still holds its original element, and a one-element array is trivially sorted. ✓
• Maintenance. Assume the invariant entering the iteration for some $j$: the prefix $A[\mathrm{1..}j-1]$ is a sorted arrangement of the original first $j-1$ elements. Line 2 copies $A[j]$ into $key$, so we may treat cell $j$ as a hole. Each pass of the while loop (lines 4–6) fires only when $A[i]>key$; line 5 copies that element one slot right into the hole, and line 6 makes cell $i$ the new hole. Ignoring the hole, every shift leaves the prefix's elements intact and in the same relative order, so the region right of the hole (through cell $j$) stays sorted and consists entirely of elements $>key$. The loop exits in one of two ways: $i=0$, so every prefix element was $>key$ and the hole is cell $1$; or $A[i]\le key$, so the hole sits just right of the rightmost element $\le key$. Either way, everything left of the hole is $\le key$ and sorted, everything right of it through cell $j$ is $>key$ and sorted, and line 7 drops $key$ into the hole. The result is $A[\mathrm{1..}j]$ sorted, holding exactly the original elements of $A[\mathrm{1..}j]$. That is the invariant with $j+1$ in place of $j$. ✓
• Termination. The for loop exits when $j$ reaches $n+1$. Plugging $j=n+1$ into the invariant: $A[\mathrm{1..}n]$ consists of exactly the elements originally in $A[\mathrm{1..}n]$, in increasing order. That is word for word the sorting specification (a sorted permutation of the input), and line 8 returns it. ✓

The maintenance step above quietly ran a second induction: the claim about holes and shifted elements is itself an invariant of the inner while loop, checked once per shift. For nested loops that layering is the normal shape of a correctness proof — an outer invariant whose maintenance step leans on an inner one. Here the inner argument is short enough to inline; when it is not, state the inner invariant explicitly and give it the same three-part treatment.

Aside: soundness and completeness

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$. Its correctness has two independent halves, and they carry standard names worth adopting now — they recur across the whole course, in search, decision procedures, verifiers, and the reductions of intractability:

• Soundness — every found answer is true. The procedure never lies in the affirmative: when it says found, genuinely $k\in A$. Soundness rules out false positives.
• Completeness — every true case is caught. The procedure never misses: when $k\in A$, it really does say found. Completeness rules out false negatives.

The two are genuinely separate. An algorithm that always answered not found would be vacuously sound — it never makes a false claim of membership — yet hopelessly incomplete; one that always answered found would be complete but unsound. Correctness requires both guarantees at once.

from typing import Optional, Sequence, TypeVar

Element = TypeVar("Element")

def contains(array: Sequence[Element], key: Element) -> bool:
  """
    Whether `key` occurs anywhere in `array`.\n
  """
  return index_of(array, key) is not None

def index_of(array: Sequence[Element], key: Element) -> Optional[int]:
  """
    The index of the first occurrence of `key` in `array`, or None if it\n
    is absent. Returning the witnessing position makes soundness manifest:\n
    a non-None answer is backed by an element actually equal to `key`.\n
  """
  # scan left to right, returning the first position whose element matches.
  for index in range(len(array)):
    if array[index] == key:
      return index

  return None

Both tools at once: binary search

Invariants are not only about prefixes growing left to right. When the array is sorted, we can search it by repeatedly halving a window, and the invariant describes where the answer can still hide rather than what has been built so far.

The invariant is deliberately conditional. It does not claim $k$ is in the window — $k$ may not be in the array at all — only that the cells outside the window have been legitimately ruled out.

• Initialization. Lines 1–2 set $lo=1$ and $hi=n$, so the window is the whole array and the claim is vacuous: if $k$ is in $A[\mathrm{1..}n]$, it is in $A[\mathrm{1..}n]$. ✓
• Maintenance. Suppose the invariant holds entering an iteration and line 5 does not return, so $A[mid]\ne k$. If $A[mid]<k$ (line 6), sortedness gives $A[1]\le \cdots \le A[mid]<k$, so no cell at index $\le mid$ can hold $k$. If $k$ is in the array at all, the invariant places it in $A[lo..hi]$, and we just excluded $A[lo..mid]$, so it lies in $A[mid+\mathrm{1..}hi]$ — exactly the new window after $lo\leftarrow mid+1$. The case $A[mid]>k$ (line 7) is symmetric. ✓
• Termination. Two duties here, and the first is easy to forget: the loop must actually end, and the exit state must imply the postcondition. For progress: $lo\le hi$ inside the loop forces $lo\le mid\le hi$, so line 6 raises $lo$ by at least one and line 7 lowers $hi$ by at least one; the window length $hi-lo+1$ strictly shrinks every iteration and the loop runs at most $\lceil \lg n\rceil +1$ times. For the exit itself there are two doors. Through line 5, the algorithm just witnessed $A[mid]=k$, so found is sound. Through line 3 failing, $lo>hi$ and the window is empty; the invariant says that if $k$ were in the array it would be in that empty window, which is absurd, so $k\notin A$ and not found is correct — the algorithm is complete. ✓

The same vocabulary as $\text{Linear-Search}$, but here completeness is not a one-line observation: it rests entirely on the invariant. Every discarded cell was ruled out for a reason, and the invariant records those reasons.

How invariant proofs go wrong

An invariant proof has exactly three joints, and each one has a characteristic failure. All three failures look like proofs until you press on the right spot.⁵

False at initialization. The seed $x\leftarrow A[1]$ in $\text{Find-Max}$ looks fussier than the neutral seed $x\leftarrow 0$, and the neutral seed is a genuine bug. With $x=0$, the invariant $x=\max \left\{A[1],\dots ,A[i-1]\right\}$ is already false entering $i=2$ whenever $A[1]\ne 0$; and on an all-negative array the if never fires, so the algorithm returns $0$ — a value that is not even in the array. The failed initialization check is not pedantry; it points at a real input that breaks the program.

Too weak to imply the postcondition. Take insertion sort and drop the permutation clause, keeping only "$A[\mathrm{1..}j-1]$ is sorted." Now consider this impostor, which replaces lines 2–7 of Algorithm 2 with a single assignment:

The weak invariant sails through all three checks: a one-cell prefix is sorted (initialization); appending a copy of the last element keeps a sorted prefix sorted (maintenance); at $j=n+1$ the whole array is sorted (termination). Every step is airtight, and the program is garbage — on $⟨5,2,4,1⟩$ it sorts to $⟨5,5,5,5⟩$. Nothing in the proof was wrong; the invariant proved a true statement that fails to imply the specification, which demanded a sorted permutation of the input. When the termination step ends with anything short of the postcondition, word for word, the invariant needs strengthening.

Off-by-one at the exit. The termination step must use the exact negation of the loop guard, evaluated at the actual exit value of the counter. $\text{Find-Max}$'s loop ends with $i=n+1$, not $i=n$; plugging the wrong value into the invariant proves only $x=\max \left\{A[1],\dots ,A[n-1]\right\}$, which leaves $A[n]$ unaccounted for. The same slip in $\text{Binary-Search}$ is a live bug rather than a weak conclusion: change line 3 to while $lo<hi$ and, on a one-element array with $A[1]=k$, the loop body never runs and line 8 answers not found. The invariant itself survives untouched — what breaks is the exit analysis, because $lo<hi$ failing gives $lo\ge hi$, a window that may still hold one unexamined cell, and the window is empty step of the termination argument is simply false.

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 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.

Further frontiers

The four deliverables are a working discipline, but each has grown into a field of its own. The precise, mechanical procedure we relied on informally has an exact meaning: a function is computable if some Turing machine computes it, and the Church–Turing thesis holds that every reasonable model of computation — Turing machines, the lambda calculus, the RAM of the next lesson — computes exactly the same class of functions. Turing's 1936 construction also produced the first problem that no algorithm can solve, the halting problem: there is no procedure that decides, for an arbitrary program and input, whether the program eventually stops.⁶ So write an algorithm for it is not always a request that can be met, a boundary worth knowing before spending a week on a problem that is provably undecidable.

The proof-of-correctness deliverable, done here by hand, can be machine-checked. Interactive proof assistants such as Coq and Isabelle let one state an algorithm's specification and its invariants formally and have the computer verify every step; the CompCert C compiler and the seL4 operating-system kernel are large systems proved correct this way, insertion sort's loop invariant scaled up to tens of thousands of lines.⁷ And the high-level-idea deliverable is where the standard design paradigms live — divide-and-conquer, greedy, dynamic programming, and the rest — each a reusable pattern for the idea step, and each the subject of a later module. Skiena frames the whole design manual around recognizing which paradigm a new problem fits.⁸

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. State which moment your invariant describes.
• Invariants must be strong enough to imply the postcondition: insertion sort's invariant needs the permutation clause, not just the prefix is sorted — $\text{Copy-Left}$ satisfies the weak version while destroying the input.
• The termination step has two duties: show the loop ends (a quantity that strictly shrinks), then combine the invariant with the exact negation of the guard at the counter's real exit value. Off-by-ones live here.
• 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. $\text{Binary-Search}$ needs both: found is witnessed directly; not found is forced by the invariant.
• Correctness and efficiency are separate questions: an algorithm can win one and lose the other.