What an algorithm actually is, why a correct one is not automatically a good one, and the argument that efficiency is a technology you can buy with thought rather than with hardware.
Chapter 1 is the shortest chapter in CLRS and the only one with no pseudocode in it. It is tempting to skip. Do not: it sets two definitions that the other thirty-four chapters lean on constantly — what counts as a problem versus an instance, and what it means for an algorithm to be correct — and it makes the case, with numbers, that the choice of algorithm can outweigh a thousandfold difference in hardware. Everything after this chapter is machinery in service of that claim.
CLRS gives a deliberately plain definition:
Three words in that sentence are load-bearing. Well-defined means every step is unambiguous: a human or a machine following the procedure has no choices left to make. Finite rules out procedures that spin forever. And the pairing of input with output is what lets us specify an algorithm without describing how it works — you state the relationship you want between the two, and any procedure that establishes it is a solution.
That input/output relationship is called the problem. Here is the one CLRS uses throughout Part II, stated in the book’s format:
The sorting problem
Input: A sequence of n numbers ⟨a₁, a₂, …, aₙ⟩.
Output: A permutation (reordering) ⟨a′₁, a′₂, …, a′ₙ⟩
of the input sequence such that
a′₁ ≤ a′₂ ≤ … ≤ a′ₙ.Notice what is not here: no mention of comparisons, swaps, recursion, or arrays. The problem says what must be true of the answer, not how to get it.
The word permutation is doing real work in that statement. Without it, the output ⟨1, 2, 3⟩ would be a valid answer to every input, since it is sorted. Requiring a permutation of the input forces the algorithm to keep exactly the elements it was given, with their multiplicities.
An instance of a problem is one specific input satisfying the problem’s input constraints. For the sorting problem, ⟨31, 41, 59, 26, 41, 58⟩ is an instance, and ⟨26, 31, 41, 41, 58, 59⟩ is the output any correct sorting algorithm must produce for it. The problem is the infinite family; the instance is one member of it.
That gives the definition of correctness:
Two consequences are worth sitting with. First, correctness is universally quantified — it is a statement about every instance, which is exactly why testing cannot establish it and why the book proves loop invariants instead. Second, an algorithm that fails to halt on some input is incorrect, even if it never produces a wrong answer. Non-termination is a correctness bug, not a performance bug.
The chapter surveys where algorithms actually show up, and the list is worth keeping because each entry is a forward pointer into the book. The practical problems that need algorithmic solutions share two features: they have many candidate solutions, most of them wrong or bad, and they have practical applications that make finding the good one worth the effort.
| Domain | The algorithmic problem underneath | Where CLRS covers it |
|---|---|---|
| Biology / genomics | Aligning and matching DNA sequences; finding similar substrings in enormous strings | Ch 14 (dynamic programming), Ch 32 (string matching) |
| The internet | Routing data along good paths; indexing and searching vast page collections | Ch 22–23 (shortest paths), Ch 11 (hash tables) |
| Electronic commerce | Public-key cryptography and digital signatures, so value can move privately | Ch 31 (number-theoretic algorithms) |
| Manufacturing and logistics | Allocating scarce resources to maximise a linear objective | Ch 29 (linear programming), Ch 24 (max flow) |
| Build systems, schedulers | Ordering parts or tasks so every dependency comes first | Ch 20 (topological sort of a DAG) |
| Signal and image processing | Converting between time and frequency representations quickly | Ch 30 (the FFT) |
| Everyday software | Keeping a collection sorted, searchable, and cheap to update | Ch 6–13 (sorting and data structures) |
The shortest-path entry deserves a note, because it recurs in the chapter as an illustration. If you have a road map and want the shortest route from one intersection to another, the number of possible routes is astronomical, yet you can find the best one in time roughly proportional to the size of the map. That gap — astronomically many candidates, but a fast way to the best — is the shape of nearly every satisfying result in the book.
The chapter introduces the second half of the book’s subject matter:
Then it adds the sentence that Part III spends four chapters justifying:
No single data structure works well for all purposes. Every structure is a bargain. An array gives you constant-time access by index and pays for it with expensive insertion in the middle. A linked list reverses that trade exactly. A hash table gives expected constant-time lookup by key but abandons ordering, so it cannot answer “what is the next largest key?” A balanced search tree keeps order and pays a logarithmic factor for every operation. Knowing which bargain you are signing is most of what Part III teaches.
| Structure | What it makes cheap | What it makes expensive | Chapter |
|---|---|---|---|
| Array | Access by index, in Θ(1) | Insert or delete in the middle, Θ(n) | 10 |
| Linked list | Insert or delete at a known position, Θ(1) | Finding that position, Θ(n) | 10 |
| Stack / queue | Push and pop, or enqueue and dequeue, in Θ(1) | Reaching anything not at the end | 10 |
| Hash table | Search, insert, delete in Θ(1) expected | Any ordered query; worst case degrades | 11 |
| Binary search tree | Ordered queries: min, max, successor, range | Θ(n) per operation if it degenerates | 12 |
| Red-black tree | All of the above in O(lg n) worst case | Rebalancing code, and constant factors | 13 |
Most of CLRS is about problems we can solve efficiently. Chapter 1 flags the exception up front: some problems have no known efficient algorithm, and a large family of them — the NP-complete problems — are all equivalent in a precise sense.
The chapter gives three reasons NP-complete problems are worth your attention:
P ≠ NP question, the most famous open problem in the field.That third point is the one to remember, because it kills the intuition that “this looks similar to something easy, so it should be easy.”
| Efficiently solvable | NP-complete or NP-hard | The difference |
|---|---|---|
| Shortest simple path between two vertices | Longest simple path between two vertices | One word |
| Euler tour: a cycle using every edge exactly once | Hamiltonian cycle: a cycle visiting every vertex exactly once | Edges instead of vertices |
| Fractional knapsack, solved greedily | 0-1 knapsack, where items cannot be split | Whether you may take half an item |
| 2-CNF satisfiability | 3-CNF satisfiability | One more literal per clause |
Knowing an NP-complete problem when you see one is a practical skill, not an academic one. If a problem at work is NP-complete, you stop hunting for the exact fast algorithm and start choosing among the three honest alternatives: solve a restricted version, accept an approximation with a proven quality bound (Chapter 35), or accept exponential worst-case time with heuristics that behave well on your real inputs.
The 4th edition uses Chapter 1 to flag two settings where the standard assumptions — one processor, all the input available up front — do not hold. Both get their own chapter in Part VII.
Clock speeds stopped climbing; core counts did not. A modern machine gets faster by doing several things at once, so an algorithm that cannot be decomposed into independent work leaves most of the machine idle. Chapter 26 develops task-parallel algorithms, where you express the available parallelism and a scheduler assigns it to cores. The analysis changes shape: instead of one running time you measure work (total operations) and span (the longest dependent chain), and their ratio bounds how much parallelism you can actually exploit.
The usual model hands you the whole input before you must answer. An online algorithm receives its input piece by piece and must commit to a decision on each piece before seeing the rest, with no chance to revise. A cache eviction policy is the canonical example: you must choose what to evict now, without knowing what will be requested next. The quality measure changes too — you compare against the best possible offline algorithm that saw everything in advance, and the ratio is the competitive ratio. Chapter 27 covers this.
Section 1.2 opens with a thought experiment. Suppose computers were infinitely fast and memory were free. Would you still have any reason to study algorithms?
CLRS answers yes, and the reason is worth stating carefully: you would still need to demonstrate that your method terminates and does so with the correct answer. Correctness is not a performance concern. An infinitely fast machine running an incorrect procedure produces wrong answers instantly, and an infinitely fast machine running a non-terminating procedure produces nothing at all, forever. So even in that fantasy, half of this book still applies.
But the fantasy is false, and that brings in the other half:
The framing here is the point of the whole chapter. Efficiency is not a nice-to-have that you attend to after the program works. It is a resource-allocation discipline, and the algorithm is the lever with the longest arm.
CLRS backs the claim with a concrete head-to-head, and this worked example is the single thing most worth carrying out of Chapter 1. It pits two sorting algorithms you meet properly in Chapter 2 against each other, but you only need their running times here:
c₁n² to sort n items. The constant c₁ is small — the inner loop is tight.c₂n lg n. The constant c₂ is larger, because of the recursion and the merging.For small n, the smaller constant wins and insertion sort is genuinely faster. The interesting question is what happens as n grows, and CLRS stacks the deck as hard as it can against merge sort to answer it:
| Computer A | Computer B | |
|---|---|---|
| Speed | 1010 instructions per second | 107 instructions per second — 1000× slower |
| Algorithm | Insertion sort | Merge sort |
| Programmer | World-class, coding in machine code | Average, coding in a high-level language |
| Compiler | None needed | Inefficient |
| Resulting cost | 2n² instructions | 50 n lg n instructions |
Every advantage that money and talent can buy sits with Computer A. Now sort ten million numbers.
Computer A — insertion sort, n = 10⁷
2 · (10⁷)² instructions
———————————————————— = 2 × 10⁴ seconds ≈ 5.5 hours
10¹⁰ instructions/sec
Computer B — merge sort, n = 10⁷
50 · 10⁷ · lg(10⁷) instructions lg(10⁷) ≈ 23.25
——————————————————————— ≈ 1163 seconds ≈ 20 minutes
10⁷ instructions/secThe slower machine, the worse programmer, and the worse compiler beat the fast machine by a factor of about 17. The only thing Computer B had going for it was the algorithm.
Push the input size up by another factor of ten and the gap becomes absurd:
Input size n | Computer A — insertion sort | Computer B — merge sort | B’s advantage |
|---|---|---|---|
| 105 | 2 seconds | 8.3 seconds | A wins, 4× |
| 106 | 200 seconds | 100 seconds | B wins, 2× |
| 107 | 5.5 hours | 20 minutes | B wins, 17× |
| 108 | 23 days | 3.7 hours | B wins, 150× |
Read that table left to right along the bottom two rows. Computer A’s thousandfold hardware advantage is a fixed multiplier; it shifts the curve down but does not change its shape. The n² term keeps growing faster than the n lg n term, so the crossover is inevitable and everything past it belongs to the better algorithm. Buying faster hardware buys you a constant factor. Choosing a better algorithm changes the exponent.
n lg n curve no matter how favourable the constants, and the gap after the crossover keeps widening. This plots instruction counts only, where 2n² and 50 n lg n meet at n ≈ 190; feed in the 1000× machine-speed difference from the table above and the break-even in wall-clock time moves out to n ≈ 470,000.n = 10⁵ under these constants Computer A still wins, and the two only break even around n ≈ 470,000. Asymptotics describe behaviour as n grows without bound, and real inputs are finite. This is exactly why production sort implementations are hybrids that switch to insertion sort on small subarrays. Chapter 3 makes the notion of “as n grows” precise so you can tell which regime you are in.The chapter closes 1.2 by asking whether algorithms are really that important, given everything else in a modern system: fast hardware, graphical interfaces, object-oriented systems, integrated web technologies, fast networking.
The answer is that algorithms sit underneath all of them. Hardware is designed with algorithms. Graphical interfaces depend on them. Routing in networks relies on them heavily, as do the compilers, interpreters, and assemblers that make high-level languages possible. Algorithms are, in the book’s phrase, at the core of most technologies used in contemporary computers.
And the trend runs the right way. As computers get faster and memory gets cheaper, we do not stop caring about efficiency — we point the extra capacity at larger problems, and larger n is precisely where algorithmic differences dominate. Faster hardware makes the choice of algorithm matter more, not less.
New in the 4th edition, and a fair question for anyone reading this in the 2020s: if a model can learn the mapping from data, why hand-design algorithms at all?
CLRS answers by describing machine learning as a way to compute when you do not know how to specify the computation. A learning method uses data to build its own procedure, which makes it the right tool when the problem is poorly understood, hard to state precisely, or drifting over time. Recognising objects in images and translating between languages are problems nobody can write a clean specification for; learning from examples is the only approach that works.
But the converse holds just as firmly. When the problem is well understood, a designed algorithm wins, and not narrowly:
| Designed algorithm | Learned model | |
|---|---|---|
| Best when | The problem has a precise specification | The specification is unknown or shifting |
| Correctness | Provable for every instance | Statistical, measured on held-out data |
| Cost | Analysable up front, in the worst case | Depends on training and inference, empirically |
| Sorting a list | Θ(n lg n), exactly right, always | No reason to attempt this |
Nobody trains a model to sort an array or find a shortest path, because we know how, and knowing how yields guarantees that a learned approximation cannot offer. The book also notes that data science — extracting knowledge from data — leans on the algorithms in this book directly, machine learning among them. The two are layered, not opposed.
n lg n algorithm at n = 10⁷, and loses by 150× at n = 10⁸. Hardware buys a constant; the algorithm changes the exponent.Chapter 2 makes all of this concrete. It gives insertion sort in full pseudocode and proves it correct with a loop invariant, which is the technique that discharges the universal claim in the definition of correctness. Then it introduces the analysis machinery that produced the c₁n² and c₂n lg n figures used above, and derives merge sort by divide-and-conquer along with the recurrence that describes its cost. Chapter 3 then defines O, Ω, and Θ properly, so “roughly c₁n²” becomes a statement you can prove things with.