What is an Algorithm?

A Working Definition

An algorithm is a finite, unambiguous, and effective procedure that, when started on a valid input, halts after a finite number of mechanical steps and produces the correct output. Stripped of prose, this is the contract:

$\text{Algorithm} : \text{Input} \;\longrightarrow\; \text{Output}, \quad \text{in finitely many steps, by following a fixed rule.}$

Three words in that sentence carry almost all of the weight. Finite means the procedure must end — no infinite loops on valid inputs. Unambiguous means the next step is always determined: there is no "and then guess." Effective means each step can actually be executed by a person with pencil and paper, or, equivalently, by a machine with no intelligence of its own.

Intuition. A recipe is the everyday word for algorithm. "Beat eggs until stiff" would not survive a computer-science definition (when does "stiff" happen?). But "beat eggs for 90 seconds at speed 8" would: it has an input (the eggs), a clear stopping rule, and steps that can be executed without judgment.

The point of insisting on this contract is that it lets us reason about a procedure mathematically: we can prove it terminates, prove it is correct, and quantify how long it takes, because the rules of the game are pinned down before the analysis starts. Everything else in this book — sorting, searching, graphs, dynamic programming, NP-hardness — is built on top of these three words.

From al-Khwarizmi to Turing

The word algorithm is a Latinized rendering of al-Khwarizmi, the 9^th-century Persian scholar Muhammad ibn Musa al-Khwarizmi. Around 825 CE, working in Baghdad's House of Wisdom, he wrote a treatise on arithmetic with Hindu-Arabic numerals. When that treatise was translated into Latin in the 12^th century as Algoritmi de numero Indorum("al-Khwarizmi on the Indian numbers"), Europeans began calling any step-by-step calculation an algorism, and the modern word algorithm grew out of that.

But algorithms predate the word by more than a millennium. Around 300 BCE, Euclid wrote down a procedure for computing the greatest common divisor of two integers. It is still the standard algorithm taught today, more than 2,300 years later. We will trace it line by line in a moment.

Turing's 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem is the moment the informal idea of "mechanical procedure" became a mathematical object. Turing described an idealized machine with a tape, a finite state register, and a transition rule. He then showed that any procedure we would intuitively call an algorithm could be simulated by such a machine. This is the Church-Turing thesis: the informal notion of algorithm and the formal notion of Turing-machine computation coincide.

Knuth's Five Criteria

In The Art of Computer Programming (1968), Donald Knuth sharpened the definition into five conditions that an algorithm must satisfy. They have been the textbook definition ever since.

1. Finiteness. The algorithm must terminate after a finite number of steps on every valid input. Formally: there exists a function $T : \text{Input} \to \mathbb{N}$ such that the procedure halts after at most $T(x)$ steps on input $x$.
2. Definiteness. Each step is precisely and unambiguously specified. Two different machines (or two different students) executing the algorithm on the same input must perform exactly the same sequence of operations.
3. Input. The algorithm has zero or more inputs drawn from a specified set. The set itself is part of the specification: GCD on two non-negative integers is a different algorithm from GCD on two Gaussian integers.
4. Output. The algorithm produces one or more outputs that bear a specified relation to the inputs. "Specified relation" is the correctness condition — e.g. $\gcd(a, b) \mid a \;\wedge\; \gcd(a, b) \mid b \;\wedge\; \forall d : (d \mid a \wedge d \mid b) \Rightarrow d \mid \gcd(a, b)$.
5. Effectiveness. Every operation must be basic enough that it could, in principle, be done exactly and in finite time by a human with pencil and paper. "Find the smallest counterexample to the Riemann hypothesis" is not effective.

Algorithm vs. Program vs. Process

These three words are often used loosely. The distinctions matter because the rest of the book lives at all three layers.

One algorithm corresponds to many programs (Python, Rust, hand-written x86 assembly — all implementing Euclid). One program corresponds to many processes (every time anyone runs it, a new process is born). When we say algorithm X is correct, we are making a claim about the algorithm, independent of any program. When we say this implementation is fast, we are usually making a claim about the program (and its compiler, OS, and hardware). Confusing these layers is a frequent source of bugs and bad benchmarks.

The Oldest Non-Trivial Algorithm: Euclid's GCD

Let's anchor the abstract definition with a concrete algorithm that is older than calculus, older than algebra, older than printed books. The greatest common divisor of two integers $a$ and $b$, written $\gcd(a, b)$, is the largest integer that divides both. For example, $\gcd(252, 105) = 21$.

Euclid's key observation, in the language of modular arithmetic, is this identity: for any positive integers $a \geq b > 0$,

$\gcd(a, b) = \gcd(b, a \bmod b),$ with the boundary case $\gcd(a, 0) = a$.

The intuition is that any common divisor of $a$ and $b$ must also divide their difference, and more generally, must divide $a - q b = a \bmod b$ for any integer $q$. So the set of common divisors is invariant under the replacement $(a, b) \to (b, a \bmod b)$, and so its maximum — the GCD — is also invariant. We get to keep replacing until the second number is 0, at which point the first number is the GCD.

This is a tiny piece of mathematics that produces a very fast algorithm. The number of steps is $O(\log \min(a, b))$ — in fact bounded by $5 \log_{10} \min(a, b)$ by Lamé's theorem (1844), one of the first running-time analyses ever written. Every step at least halves the smaller number on average, so even on 500-digit cryptographic numbers the algorithm finishes in a couple of thousand steps.

Interactive: Stepping Through Euclid

Use the controls below to watch Euclid's algorithm reduce a pair of integers to a GCD. The blue and amber bars show the current values of $a$ and $b$, and the trace at the bottom shows every step. Try the preset 1071, 462 (which gives 21) or type your own numbers. Notice how rapidly $b$ shrinks — that is $O(\log)$ in action.

A few things to look for. First, after a single step the larger of the two arguments is gone forever — we always replace the pair with smaller numbers. Second, the algorithm cannot loop: each iteration strictly decreases the second argument (because $a \bmod b < b$), and the second argument is a non-negative integer, so it must eventually reach 0. That is a complete termination proof in two sentences, the kind of argument we will use constantly in this book.

The Same Algorithm in Two Languages

We said earlier that one algorithm can be encoded as many programs. Here is Euclid's algorithm in two different programming languages, in two different styles. The algorithm is the same; the programs are different.

Pure Python: a recursive transcription of the math

abs(-252) = 252, abs(105) = 105 -> we proceed with (252, 105).

gcd(21, 0): b == 0, return 21. Done.

gcd(252, 105): 252 mod 105 = 42, recurse on gcd(105, 42). Then gcd(42, 21). Then gcd(21, 0) = 21.

1def gcd(a: int, b: int) -> int:
2    """Greatest common divisor of two non-negative integers (Euclid's algorithm)."""
3    a, b = abs(a), abs(b)
4    if b == 0:
5        return a
6    return gcd(b, a % b)
7
8
9# Worked example
10print(gcd(252, 105))   # -> 21
11print(gcd(1071, 462))  # -> 21
12print(gcd(17, 0))      # -> 17  (boundary case)
13print(gcd(0, 0))       # -> 0   (conventional, see "Edge cases" below)

TypeScript: an iterative version that is closer to what a CPU actually does

Recursion is mathematically natural but every recursive call costs a stack frame. The same algorithm can be written iteratively with two variables and a loop. The output is identical; the runtime characteristics are slightly different (no stack growth, friendlier to tail-call-less compilers).

gcd(252, 105) -> x = 252, y = 105.

Iteration 1: x=252, y=105, y != 0, enter loop.

Iteration 1: r = 252 % 105 = 42. Iteration 2: r = 105 % 42 = 21. Iteration 3: r = 42 % 21 = 0.

Iteration 1: x becomes 105. Iteration 2: x becomes 42. Iteration 3: x becomes 21.

Iteration 1: y becomes 42. Iteration 2: y becomes 21. Iteration 3: y becomes 0 -> loop exits.

1function gcd(a: number, b: number): number {
2  // Normalize: GCD is defined for non-negative integers.
3  let x = Math.abs(a);
4  let y = Math.abs(b);
5
6  // Loop invariant: gcd(x, y) == gcd(original |a|, original |b|).
7  // Each iteration replaces (x, y) with (y, x mod y).
8  // Since y strictly decreases and stays >= 0, the loop terminates.
9  while (y !== 0) {
10    const r = x % y;
11    x = y;
12    y = r;
13  }
14  return x;
15}
16
17console.log(gcd(252, 105));   // -> 21
18console.log(gcd(1071, 462));  // -> 21
19console.log(gcd(17, 0));      // -> 17

Binary Search: Algorithm as a Decision

A second canonical example. Given a sorted array $A[0..n-1]$ and a target $t$, decide whether $t$ is in the array, and if so where. The naive algorithm is to scan from left to right — $O(n)$ comparisons. Binary search uses the sorted-ness to do dramatically better:

1. Look at the middle element.
2. If it equals $t$, return its index.
3. If it is less than $t$, recurse on the right half.
4. If it is greater than $t$, recurse on the left half.

1def binary_search(A: list[int], t: int) -> int:
2    """Return the index of t in sorted list A, or -1 if absent."""
3    lo, hi = 0, len(A) - 1
4    while lo <= hi:
5        mid = (lo + hi) // 2     # integer midpoint, no overflow in Python
6        if A[mid] == t:
7            return mid
8        elif A[mid] < t:
9            lo = mid + 1         # discard left half (incl. mid)
10        else:
11            hi = mid - 1         # discard right half (incl. mid)
12    return -1

Each iteration halves the live region of the array. After $k$ iterations the live region has size at most $n / 2^k$, so the loop exits after at most $\lceil \log_2 n \rceil$ iterations. For $n = 10^9$, that is 30 comparisons total. The difference between $O(n)$ and $O(\log n)$ is the difference between seconds and nanoseconds at production scale — and it comes from a single observation about sorted data.

Correctness: Invariants and Termination

How do we know an algorithm is correct? Not by testing it on a few examples (testing can prove the presence of bugs but never their absence, as Dijkstra famously said). We prove it.

A typical correctness proof has two halves:

1. Termination. Show the algorithm halts on every valid input. Usually done by exhibiting a variant: a quantity that strictly decreases and is bounded below.
2. Partial correctness. Show that if the algorithm halts, it halts with the correct answer. Usually done by identifying a loop invariant: a property preserved by every iteration that, combined with the loop's termination condition, implies the post-condition.

Apply this to Euclid's algorithm. Variant: $b$ — a non-negative integer that strictly decreases each iteration (because $0 \leq a \bmod b < b$). It is bounded below by 0, so the loop must terminate. Invariant: $\gcd(a, b) = \gcd(a_0, b_0)$, where $(a_0, b_0)$ are the original inputs. The recurrence $\gcd(a, b) = \gcd(b, a \bmod b)$ guarantees the invariant is preserved by each step. When the loop exits with $b = 0$, the invariant says $\gcd(a_0, b_0) = \gcd(a, 0) = a$, which is what we return. QED.

Efficiency: A First Glimpse

Correctness is necessary but not sufficient. A bubble sort and a merge sort both correctly sort an array; one is usable, the other is not, on modern data sizes. The next chapter is devoted to asymptotic analysis — the formal language for comparing algorithms. For now, an informal preview.

We measure an algorithm's cost as a function of the input size $n$. We care about how that function grows, not its constants. The standard scale:

At $n = 10^6$, an $O(n \log n)$ algorithm finishes in well under a second on a laptop. An $O(n^2)$ algorithm takes hours. An $O(2^n)$ algorithm will not finish before the heat death of the universe. Constants matter, but they cannot rescue you from the wrong asymptotic class. This is why the rest of the book obsesses over picking the right algorithm before worrying about micro-optimization.

Edge Cases and Pathological Inputs

Part of specifying an algorithm is specifying its domain. The boundaries are where bugs live. For Euclid's GCD:

• $\gcd(a, 0)$: base case, returns $a$. Defined.
• $\gcd(0, b)$: one recursive call swaps the arguments; returns $b$. Defined.
• $\gcd(0, 0)$: mathematically undefined (every integer divides 0, so there is no greatest common divisor). By convention, computer-science libraries return 0 here so that algebraic identities like $\gcd(a, b) \cdot \operatorname{lcm}(a, b) = |a \cdot b|$ stay consistent.
• Negative inputs: handled by taking $|a|, |b|$ first; some libraries instead define $\gcd(-12, 18) = 6$ by symmetry.
• Huge inputs: in Python int is arbitrary precision so it just works; in C/Java with int32_t, GCD on two 32-bit integers is safe but the product in lcm overflows.

Where Algorithms Live in the Real World

It is easy to think of algorithms as classroom toys. They are not. They are the load-bearing structure of the systems you use every second of every day.

Look at the last row of the security entry. The RSA cryptosystem, which protects nearly every TLS connection on the internet, computes a modular inverse using the extended Euclidean algorithm — a 30-line elaboration of the procedure Euclid wrote down in 300 BCE. A 2,300-year-old algorithm is, right now, the reason your connection to your bank is private. Algorithms compound across millennia.

What an Algorithm Is Not

Sharpening the boundary further. None of the following are algorithms, and recognizing why builds intuition for what an algorithm is.

We have only sketched the landscape. Across the next 14 chapters we will build the standard algorithmic toolkit — arrays, lists, stacks, queues, trees, hash tables, heaps, graphs, recursion, dynamic programming, greedy methods, divide and conquer — with the same level of mathematical care we just applied to Euclid. Every data structure we meet will have an algorithmic personality (what it makes fast, what it makes slow), and every algorithm we meet will sit on top of a data structure. The two halves of this book's title are the two halves of the same craft.