LEARN TO PROGRAM · CHAPTER 06 · INTERMEDIATE
An algorithm is a recipe precise enough for a machine. This chapter is about choosing good ones, and about the one question that decides most of that choice: when the input gets bigger, how much more work does it take?
Each idea has a bench on the ring, running a real algorithm on real data. The numbers on the benches are what the code blocks below print: change the code, and you can check them.
01 · WHAT AN ALGORITHM IS
An algorithm is a finite list of exact steps that solves a problem for any input of the right kind, and then stops. A program is an algorithm written in a particular language; the algorithm is the idea underneath, and it outlives every language.
One of the oldest still in daily use is Euclid's algorithm for the greatest common divisor, written down around 300 BC. Picture a 42 × 30 rectangle. Cut off the biggest square you can (30 × 30). From what is left (12 × 30), cut squares of 12 until you can't. Then squares of 6. Nothing is left over, so 6 is the answer: 6 × 6 tiles fill the whole rectangle exactly, and no bigger square does. That is what the first bench shows.
Try gcd(1071, 462), Euclid's own kind of example, or two consecutive Fibonacci numbers like gcd(89, 55): they are the slowest inputs there are for their size.
Notice what makes it an algorithm rather than a vague method: every step is mechanical (a remainder), there is a clear test for stopping (b === 0), and it is guaranteed to stop, because the remainder shrinks every time. Correctness and termination are the first two questions to ask of any algorithm. The third is how long it takes, and that is the rest of this chapter.
02 · COUNTING STEPS
How fast is an algorithm? Seconds are a bad answer: they depend on the machine, the language, the other programs running, even the temperature of the chip. Computer scientists count steps instead, basic operations like a comparison or an addition, as a function of the input size n.
The bench shows three loops running at the same pace, with n = 8. A single loop does 8 steps. A loop inside a loop does 8 × 8 = 64. A loop that halves its counter (8, 4, 2, 1) does only 3. Now make n a thousand:
Press Step through on a smaller list, like [4].map(countSteps), and watch the counters climb.
At n = 10,000 the nested loop does a hundred million steps while the halving loop does 13. The constant work inside each loop matters much less than its shape. You can count a real function exactly, too, but you rarely need to:
The exact count is 3n + 2. For big n the "+ 2" is noise and the 3 depends on what you call a step. What survives is "proportional to n".
03 · BIG-O, Θ AND Ω
Big-O notation keeps only that surviving shape. Drop the constants and the smaller terms: 3n + 2 becomes O(n), 5n² + 40n becomes O(n²). On the bench each curve is a glass curtain, drawn to the same scale, with n sweeping from 1 to 16. By n = 9, n² has gone through the ceiling; 2ⁿ went at n = 7.
Add a column for n ** 3 or Math.sqrt(n). Then try n = 1,000.
Precisely, there are three symbols, one for each side of the sandwich:
For n ≥ 10, 3n ≤ 3n + 10 ≤ 4n. So 3n + 10 is Θ(n): O(n) and Ω(n) together.
The gold curtain on the bench is a real sandwich: the band between ½ · n log₂ n and 1 · n log₂ n, with white dots for the comparisons merge sort actually made on the first n of the race's numbers. Every dot lands inside the band: merge sort is Θ(n log n).
The fastest way to learn what Big-O means in practice is the doubling test: double n, time it, and look at the ratio. About 2× means O(n), about 4× means O(n²), about 8× means O(n³).
Timers in a browser are noisy, so the ratios wobble around 4. The prediction on the last line is the real point.
Common orders, from best to worst: O(1) (array index, hash lookup on average), O(log n) (binary search), O(n) (one pass), O(n log n) (good sorting), O(n²) (all pairs), O(2ⁿ) (all subsets), O(n!) (all orderings).
04 · SEARCHING
Linear search checks items one at a time until it finds the target: O(n). It works on anything, sorted or not. Binary search needs sorted data, and repays you enormously: look at the middle, and throw away the half that can't contain the target. Each step halves what is left, so it takes at most about log₂ n steps.
On the bench both look for 53 in the same sorted row of 32. Linear needs 23 checks. Binary needs 5, and the dimmed bars are the ones it never had to look at.
Search for a number that isn't there, like 54. Linear has to look at everything; binary still takes at most 6 steps.
Step through a small one and watch lo and hi close in:
Change target to 30, which isn't there, and watch lo pass hi.
Binary search is everywhere once you look. Python ships it as bisect. Databases use the same idea on disk: a B-tree index turns a full table scan into a few page reads.
import bisect
row = [2, 3, 5, 8, 9, 12, 14, 17, 19, 21]
i = bisect.bisect_left(row, 17) # binary search, from the standard library
print(i, row[i] == 17) # 7 True
-- A table of 10 million users, searched by email.
SELECT * FROM users WHERE email = 'ada@example.com';
-- Without an index: the database reads every row. Θ(n)
-- Seq Scan on users (rows=10000000)
CREATE INDEX users_email ON users (email);
-- With a B-tree index: a few page reads, top to bottom. O(log n)
-- Index Scan using users_email on users (rows=1)
05 · SORTING RACE
Sorting is the most studied problem in computing, because so much else gets easier once data is in order: binary search, finding duplicates, merging, ranking. On the bench, five classic sorts race on the same 24 numbers, one operation per tick. White flashes are comparisons, pink are writes. The counters are live.
These are the exact counts on the bench. Swap the data for [...data].sort((a, b) => a - b) (already sorted) and watch bubble and insertion win while quicksort collapses.
Now with 2,000 random numbers, where the shape of the curve takes over:
You will almost never write these for real work. JavaScript's Array.prototype.sort in V8 has been TimSort since 2018: a merge sort that finds runs already in order and uses insertion sort for short pieces. The language spec has required the sort to be stable since ES2019. Python's list.sort is a close cousin, and C's qsort is whatever your C library chose.
Step through it. Watch j walk left and the bigger items shift right to make room for x.
#include <stdlib.h>
int cmp(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y);
}
int main(void) {
int a[] = {17, 4, 22, 9, 1};
qsort(a, 5, sizeof a[0], cmp); /* C's library sort */
return 0;
}
06 · DIVIDE AND CONQUER
A recursive function solves a problem by calling itself on a smaller version of it, until it reaches a base case small enough to answer directly. Every call gets its own frame on the call stack, which is how each one keeps its own n.
Press Step through and watch the call stack grow to five frames, then unwind as each one adds its n.
Divide and conquer is recursion with a plan: split the problem into parts, solve each part recursively, combine the answers. Merge sort is the textbook case, and the bench shows it as an hourglass: eight bars split down to single items (a list of one is already sorted), then merge back up in order.
The indentation is the depth of the recursion. Compare it with the hourglass, row by row.
Why n log n? Halving 8 takes log₂ 8 = 3 levels. On every level, merging touches each of the n items once. So the work is n per level × log n levels. Written as a recurrence: T(n) = 2T(n/2) + n, which solves to Θ(n log n). The "master theorem" in every algorithms textbook solves recurrences like this one by formula.
Recursion has a cost of its own: each frame takes stack memory, and the stack is small.
A RangeError: the stack ran out. Any recursion can be rewritten as a loop with your own stack, which lives in the much bigger heap. See where the stack lives in Memory.
07 · GRAPH SEARCH
A graph is dots (nodes) joined by lines (edges): cities and roads, people and friendships, routers and cables, web pages and links. Many problems become "find a path" or "visit everything" on a graph. The bench runs three classic searches from A on the same twelve-node graph, in turn.
The same orders as the bench. Change the weight of A–C from 2 to 9 and see how Dijkstra's answer changes while BFS doesn't care.
All three are O(V + E) or close: every node and edge is handled a bounded number of times. Our Dijkstra scans for the closest node each round, which is O(V²); with a binary heap it is O((V + E) log V). Python has the heap in its standard library:
import heapq
def dijkstra(adj, start):
dist = {start: 0}
heap = [(0, start)] # (distance, node), smallest on top
while heap:
d, u = heapq.heappop(heap)
if d > dist.get(u, float("inf")):
continue # a stale entry: skip it
for v, w in adj[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist # O((V + E) log V)
This is not a classroom toy. Routers running OSPF use Dijkstra's algorithm to compute their routes through the network, which is part of how a packet finds its way across the internet.
08 · DYNAMIC PROGRAMMING
The obvious recursive Fibonacci is beautiful and terrible. To get f(6) it computes f(4) twice, f(3) three times and f(2) five times. The bench draws the whole call tree first, all 25 calls of it. The tree grows by about 1.6× with every step of n, so it is exponential: f(30) takes 2,692,537 calls.
Dynamic programming fixes that with one idea: store each answer the first time and look it up after. With a memo, the same tree collapses to 11 calls (the ✓ nodes are lookups), and the table underneath fills from f(0) to f(6).
Try fibSlow(35): it takes seconds. fibMemo(1000) is instant. At fibMemo(1500) the answer overflows a double and becomes Infinity.
DP works when a problem has two properties: optimal substructure (the best answer is built from best answers to smaller problems) and overlapping subproblems (the same small problems come up again and again). There are two ways to write it: top-down with a memo, as above, or bottom-up, filling a table in an order where everything you need is already there.
A real one: edit distance, the fewest single-letter edits that turn one word into another. Spell checkers use it to suggest words; tools like diff and DNA alignment use close relatives. Each cell is the cheapest of three moves from its neighbours:
kitten → sitting is 3: k→s, e→i, insert g. The table is O(n × m) time and space; keeping only two rows makes the space O(m).
09 · TIME VS SPACE
Memory is the other resource an algorithm uses, and Big-O measures it the same way: how the extra memory grows with n. Very often you can trade one for the other. The bench solves two-sum (find two numbers that add up to 13) both ways on the same eight numbers.
On the left, every pair is tried in turn: O(n²) time and nothing remembered. On the right, each number goes into a hash map (bucket = value mod 8; 3 and 11 share bucket 3, a collision, so they stack). Before storing a number, it asks the map for its partner. Six steps, five numbers remembered.
The same answer, [2, 5], by both routes. At n = 8 the difference is 16 checks against 6 steps; at n = 100,000 it is billions against a hundred thousand.
The memo in the last act was the same trade: 29 stored numbers bought a speed-up from 2.7 million calls to 59. So is a lookup table, computed once and reused forever:
256 bytes of table make every popcount 4 lookups. CPUs now have a single instruction for it, which is the same trade made in silicon.
The trade isn't always worth it. Memory isn't free: a cache miss costs far more than an addition, so a smaller structure that fits in the CPU's cache can beat a "faster" one that doesn't. See how deep that hierarchy goes in Memory and Inside the CPU. And recursion uses space too: one stack frame per level, so merge sort needs O(log n) of stack on top of its O(n) buffer.
10 · P VS NP
Some problems seem to have no fast algorithm at all. Subset sum: given some numbers, is there a selection that adds up exactly to a target? With 6 items there are 2⁶ = 64 selections, which the bench's cone shows as yes/no choices, one level per item. The brute force walks every leaf. With 60 items there are about 10¹⁸.
But checking an answer is easy: if someone hands you {4, 5}, you add two numbers. That gap between finding and checking is the heart of the most famous open question in computer science.
The question: is P = NP? If any NP-complete problem has a polynomial algorithm, they all do. Nobody has found one, and nobody has proved one can't exist. It is one of the Clay Institute's seven Millennium Prize Problems, with a million dollars for a proof either way.
11 · PRACTISING PROBLEMS
Coding interviews at many companies ask you to solve a small algorithm problem in about 45 minutes while talking. It is a skill of its own, separate from building software, and it responds well to practice. What works is the same as for any skill: deliberate, spaced, and checked against tests.
// The shape of every problem you solve under a clock.
// 1. Restate it, and ask: input size? sorted? duplicates? negatives? empty?
// 2. Work two examples by hand, one of them awkward (empty, one item, all equal).
// 3. Say the brute force out loud, and its Big-O.
// 4. Find the bottleneck. Which pattern removes it?
// repeated lookups → a hash map or set
// sorted input → binary search, two pointers
// contiguous runs → sliding window
// "shortest" in a grid → BFS
// "best" with overlap → dynamic programming
// "top k" → a heap
// 5. Write it. Name things well. Talk while you type.
// 6. Test it by hand on your examples, then the edge cases.
// 7. State the final time and space complexity.
Learn patterns, not problems. A few hundred well-known problems reduce to about fifteen patterns: hash map lookups, two pointers, sliding window, binary search (including on the answer), BFS and DFS, heaps for "top k", intervals, backtracking, dynamic programming. When you finish a problem, write one line: which pattern, and what clue in the question pointed to it.
Time-box it. Give a problem 25 to 30 minutes. If you are stuck, read only the first hint, or the solution's idea, then close it and write the code yourself. Mark the problem and solve it again cold in three days and again in two weeks. The re-solve is where the learning sticks.
Talk out loud. Interviewers grade your reasoning, not just the answer. Practise saying the brute force and its Big-O first, then improving it. A mock interview with a friend each week is worth more than ten problems alone.
Where this leads: algorithms run on real machines, and the next chapters keep returning to cost. A query planner choosing between an index and a scan is doing this chapter's arithmetic. So is a cluster spreading work across machines, or a GPU doing thousands of the same step at once.
PRACTICE
Type the code yourself rather than pasting it: producing an answer builds memory that reading does not. Use the hints one at a time.
Return the index of target in the sorted array, or -1 if it isn't there. No indexOf: keep a range lo..hi and halve it every step. The check tries the first item, the last, a missing one and an empty array, which is where binary searches usually break.
Write insertion sort: walk left to right, and slide each new item left until the one before it is not bigger. Sort the array in place and return it. Don't call .sort().
This works, but compares every pair. The check runs it on 300,000 numbers, about 45 billion comparisons, so it will time out. Make it O(n) by remembering what you have already seen.
Return the fewest steps from S to E moving up, down, left or right, never through #. Return -1 if there is no way. This maze needs 12.
minCoins(coins, amount) should return the fewest coins that add up to amount, or -1 if it can't be done. The starter is greedy (always take the biggest coin that fits). Run it on [1, 3, 4] and 6: it says 3 (4+1+1), but 3+3 needs only 2. Fix it with a table.
Return the indices [i, j] (with i < j) of the two numbers that add up to target. The check includes 200,000 numbers with the pair at the very end, so try-every-pair will be too slow.
RECALL
Answer each one before you open it. Then come back tomorrow, and again next week, and answer them cold: retrieval spaced over days is the most reliable study method we know of. Why that works.
An algorithm is O(n²). What does that tell you, and what doesn't it?
How many steps does binary search need for a billion sorted items? What must be true first?
Merge sort and quicksort are both O(n log n) on average. Where do they differ?
BFS, DFS, Dijkstra: which data structure drives each, and what does each find?
What two properties make a problem a good fit for dynamic programming?
Does NP mean "not polynomial"?
GO FURTHER
SOURCES