Algorithms
Defining the Algorithm
An algorithm is a finite sequence of well-defined instructions for solving a problem, guaranteed to halt and produce a correct answer for every valid input. The word descends from the name of the ninth-century Persian mathematician al-Khwārizmī, whose systematic arithmetic methods were translated into Latin and shaped European mathematics for centuries. Long before computers existed, humans relied on algorithms: Babylonian scribes computed square roots, Euclid described his famous method for greatest common divisors around 300 BCE, and Chinese mathematicians solved systems of linear equations by elimination.
Three properties distinguish a true algorithm from a vague approach. First, precision: each step must be unambiguous, executable without interpretation or creativity. Second, finiteness: the procedure must terminate after a bounded number of steps. Third, generality: it must work for the entire class of inputs it claims to handle, not merely convenient cases. A procedure that usually works but occasionally loops forever or returns nonsense is not yet an algorithm.
Correctness
An algorithm earns trust through proof, not testing alone. Computer scientists distinguish two claims. Partial correctness says: if the algorithm terminates, its output satisfies the specification. Total correctness adds termination itself. Both are established mathematically, typically using a loop invariant — a statement that holds before and after every iteration and, combined with the exit condition, implies the final result.
The value of proofs became vivid in 2008, when researchers found a bug deep in a widely used sorting routine that had gone undetected for sixteen years despite enormous test exposure. Testing explores only finitely many inputs; proofs cover them all. In practice, careful engineers use both: proofs or formal verification for critical cores, extensive testing for everything else.
Big-O Intuition
Not all correct algorithms are equal. Searching a phone directory page by page finds a name eventually; opening the book to the middle, checking whether your target falls before or after, and repeating halves the remaining pages each time. For a thousand entries, the first method inspects up to a thousand pages, the second about ten. For a billion entries, the gap explodes to a billion versus thirty.
Computer science captures this with asymptotic notation, most famously big-O, which measures how the number of basic operations grows as input size n increases, ignoring constant factors and lower-order terms. An algorithm that does a constant amount of work per element runs in O(n) — linear time. Halving the problem repeatedly yields O(log n), logarithmic time. Comparing every pair of elements gives O(n²), quadratic time, which becomes painful quickly. Sorting methods based on clever divide-and-conquer achieve O(n log n).
The intuition to internalize: growth rates dominate constants once inputs grow large. A slow-in-theory algorithm with tiny constants loses to a fast-in-theory one only for modest sizes. For large data — and modern data is always large — the shape of the growth curve wins.
Classic Examples
Binary search exploits order. Given a sorted array, compare the target with the middle element; discard the wrong half; repeat. Each comparison eliminates half the candidates, so twenty comparisons suffice for a million items. Its precondition — sortedness — illustrates a broader theme: structure in data enables speed, and maintaining structure can be worth the cost.
Sorting is the field's laboratory. Insertion sort builds the sorted output one card at a time, like arranging a hand of playing cards — simple, and excellent for nearly-sorted or tiny inputs, but quadratic overall. Merge sort splits the array in half, sorts each half recursively, and merges the results, achieving O(n log n) reliably. Quicksort partitions around a chosen pivot and typically outperforms merge sort in practice thanks to cache-friendly memory access, though its worst case is quadratic. Real standard libraries use hybrid algorithms such as Timsort, which detects naturally occurring runs in real-world data and merges them — evidence that theory and pragmatism blend constantly.
Other landmarks include Dijkstra's shortest-path algorithm, dynamic programming for optimization problems, and hashing for near-constant-time lookup.
Why Algorithms Outlive Hardware
Processors double and are replaced; languages rise and fall; frameworks churn every few years. But quicksort is fifty years old and still sorting your files. Binary search dates conceptually to antiquity and now indexes billions of web documents. An algorithm is pure structure — a pattern of reasoning about information — so it transfers across technologies untouched. Learning algorithms is therefore learning the durable layer of computer science: the ideas that every machine, present and future, will execute.