Algorithms: Why Growth Beats Speed

You ask your phone for directions across a city of a million intersections and a route appears before you have put the phone down. A naive program could check every possible route. There are more routes than atoms in the universe; it would never finish. Yours finishes in a blink, because someone found a way to be clever about which routes to even consider.

That cleverness is an algorithm: a precise, step-by-step method that always finishes and always gives the right answer. The course asks of any method two questions: is it correct? and how does its work grow as the problem grows? The second question has a surprisingly sharp answer, and it is the first thing a graduate learns to see.

Big-O: growth beats constant factors

To compare methods, count steps as a function of the input size n and ignore the units. Doubling the list, how much more work? A method that does n steps doubles. One that compares every pair, n², quadruples. One that tries every subset, 2ⁿ, squares itself every time you add a single item. Big-O notation keeps only that shape: O(n), O(n log n), O(n²), O(2ⁿ).

Worked number: take one million items. An n log₂ n method needs about 20 million steps, 0.02 seconds at a billion steps a second. An n² method needs a trillion, about 16.7 minutes. Make the first method 1,000 times slower per step and it still wins once n passes about 13,700. Slide to find out.

Look at the bottom rows. At n = 60 the "try every subset" method would need about 36 years; at 20 items, "try every ordering" about 77. No faster chip rescues those, which is why computer scientists draw a hard line between methods whose cost grows like a polynomial and those that explode. We return to that line at the end.

Searching: the question that halves the world

Find a name in an unsorted list and you must look at every one, in the worst case n looks. But in a sorted list you can be smarter: open the middle, see whether you are too high or too low, and throw away half. Repeat. This is binary search, and it is how you look up a word in a paper dictionary without reading from A.

Play it from the other side. Think of a number from 1 to 1,000 and tell the page "higher" or "lower".

The price of the trick is the sorting: binary search only works because the list is in order. That is the pattern of the whole subject: pay once to arrange the data, then every later question is cheap. Even simple code gets this wrong. Computing the middle as (low + high) / 2 can overflow a fixed-size integer on arrays of about a billion items. Joshua Bloch reported in 2006 that this bug had sat in the binary search he wrote for Java's library for about nine years; we come back to why proofs matter below.

Sorting and divide and conquer

Sorting is the classic place to see growth rates fight. Insertion sort works like sorting playing cards in your hand: take each card and slide it left past bigger ones into place. It is simple, and on a shuffled list each new card travels past about half the cards before it, so the total is around n²/4 comparisons.

Merge sort uses divide and conquer: split the list in half, sort each half (by the same method, recursively), then merge the two sorted halves by repeatedly taking the smaller front card. Merging costs about n steps, and there are about log₂ n levels of halving, so the total is around n log₂ n. John von Neumann devised merge sort in 1945, and Timsort, the sort Python uses (and Java for objects), is a hybrid of merge and insertion sort.

Recursion and remembering: dynamic programming

Merge sort called itself on smaller pieces: recursion. Recursion is natural, but it can be wasteful. The Fibonacci numbers (each is the sum of the two before: 1, 1, 2, 3, 5, 8...) are defined recursively, and a direct program computes fib(n) by calling fib(n−1) and fib(n−2). Those two calls each repeat most of each other's work, and the repetition compounds: fib(40) makes 331,160,281 calls to arrive at 102,334,155.

The cure is almost embarrassingly simple: write each answer down the first time, and look it up thereafter. That is memoisation, and applying it systematically to problems built from overlapping subproblems is dynamic programming, a name Richard Bellman coined in the 1950s. With the notebook, fib(40) takes 79 calls, because each of the 40 values is computed once.

Greedy: the best move right now

Sometimes you can build the best answer by always taking the best-looking step. Giving change, you hand over the biggest coin that fits, and repeat. This is a greedy algorithm: fast, simple, and sometimes exactly right. Dijkstra's shortest-path method and Kruskal's way of connecting cities with the least cable are both greedy and provably optimal.

But greedy can be confidently wrong. In a currency with coins 1, 3 and 4, making 6 greedily gives 4 + 1 + 1 (three coins), while 3 + 3 (two coins) is better. The real question is never "does greedy work?" but "can I prove it works for this problem?". When it fails, dynamic programming, which tries every sub-answer and keeps the best, is the usual fix.

Graph algorithms: BFS, DFS and your GPS

Take a map as a graph: intersections are dots, roads are links with lengths. Three basic explorations cover most of what you will meet. Breadth-first search (BFS) visits all neighbours, then their neighbours: it finds the route with the fewest roads, using a queue. Depth-first search (DFS) plunges down one road as far as it goes, then backs up: it uses a stack, and is how a maze solver or a dependency resolver works.

Fewest roads is not shortest drive. Dijkstra's algorithm always settles the nearest not-yet-settled place by total distance, using a priority queue (the heap from the last course), and relaxes its neighbours. Edsger Dijkstra devised it in 1956, which he later called a twenty-minute invention, while sitting at a café in Amsterdam, and published it in 1959. Real route planners add speed-ups on top, such as A*.

Correctness and invariants

Fast and wrong is worthless, and testing only shows the cases you tried. The tool for certainty is the invariant: a statement that is true before a loop starts, stays true on every pass, and so, when the loop ends, says something useful. In insertion sort the invariant is: the cards already in your left hand are sorted. It holds with one card; each step slides one more card into its place without disturbing the order; so after the last card, everything is sorted. Three sentences prove it.

Binary search has an invariant too: if the target is present, it lies between low and high. Programmers who skip the proof tend to get the edges wrong, and indeed the midpoint overflow bug mentioned earlier hid for about nine years in code that looked obviously fine. A graduate does not trust a loop until they can say what stays true.

A preview of P versus NP

Some problems resist everything above. A salesman must visit 15 cities and return, as short as possible. The obvious method checks every order: (15 − 1)! / 2 = 43,589,145,600 round trips, which a billion-a-second machine does in about 44 seconds. At 25 cities there are about 3.1×10²³ trips, roughly ten million years of computing. No known method avoids this explosion in the worst case, yet checking a proposed tour against a target length is quick.

Problems like this, quick to check and apparently slow to solve, sit in a class called NP. Whether every one of them also has a fast method (P = NP?) is the most famous open question in the field; most experts believe not, and the Clay Mathematics Institute offers a million dollars for a proof either way. The next course in the path, Theory of Computation (34/29), takes this up properly.

What a graduate just sees

• Work is a function of size; the shape of that curve matters more than any constant.
• Halving is powerful: a million items, 20 questions.
• Pay to organise once, then ask cheaply many times.
• Split, solve, combine: most fast methods are divide and conquer.
• If a recursion repeats itself, write the answers down.
• Greedy is a hope until it is a proof.
• Fewest hops is not the shortest path; use the right algorithm for the right "shortest".
• A loop is trusted when you can state its invariant.
• Some problems blow up at 60 items however fast your computer is.

Where it shows up next

• Theory of Computation (34/29): what is hard in principle, and what is impossible.
• Machine Learning (34/32): training is an optimisation, and gradient descent repeats a cheap, locally best step downhill.
• Databases (34/28): sorting and joining billions of rows is the algorithms of this course at scale.
• Operating Systems (34/26) and Networks (34/27): schedulers pick the next job with a priority queue, and routers compute shortest paths across the internet.
• In life: a maps app, a spell-checker, a recommendation list, a delivery schedule.

If you want to go deeper

• 📘 Textbook: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (MIT Press, 4th ed., 2022), the standard for university courses. Sedgewick and Wayne, Algorithms (4th ed.) is code-first.
• 📘 Gentler and free: Jeff Erickson, Algorithms (free online at jeffe.cs.illinois.edu/teaching/algorithms/, also in print), clear and proof-friendly.
• 🌐 Free course: MIT OpenCourseWare 6.006, Introduction to Algorithms (Spring 2020; Demaine, Ku and Solomon), with video lectures and problem sets.
• 🌐 Free course: Harvard CS50x, Week 3 on algorithms.