Algorithms,
from zero to fluent.

A recipe that says "stir until done" works fine for a cook who can tell when it's done, but a computer needs a rule it can check mechanically, not a feeling. An algorithm is that rule made precise: a finite sequence of unambiguous steps that transforms an input into a desired output, and is guaranteed to stop. Every algorithm in this guide is a precise procedure you could carry out with pencil and paper, only faster.

Two questions decide whether an algorithm is any good. Is it correct? Does it produce the right answer on every allowed input, not just the one you tried. And what does it cost? How does the amount of work grow as the input gets bigger. Correctness without cost is a daydream (a correct method that takes a billion years is useless); cost without correctness is a fast wrong answer. The whole field lives in the tension between the two.

We measure cost by counting basic operations, not seconds on a stopwatch. Seconds depend on your laptop, the language, and what else is running. The count of comparisons or additions an algorithm performs is a property of the algorithm itself. The widget below runs the simplest useful algorithm there is, "find the largest number in a list," and counts every comparison it makes as it scans. One pass, left to right, holding the best value seen so far.

Counting exact operations is precise but fussy. What we really care about is how the count grows as the input n gets large. An algorithm that does 3n + 7 operations and one that does 100n both grow linearly: double the input and the work roughly doubles. The constants and low-order terms wash out at scale. Big-O notation throws them away on purpose and keeps only the shape of the growth.

The reason this abstraction earns its keep is that the differences between growth classes dwarf every constant factor. A quadratic algorithm on a fast computer loses to a linearithmic one on a slow computer, as soon as the input is big enough. The widget below plots the common growth classes and lets you push n up. Watch the order flip: for tiny n the curves are tangled, but by the right edge they have sorted themselves into a strict hierarchy that never reverses again.

One algorithm can have three different costs. The best case is the luckiest input, the worst case the unluckiest, and the average case what you expect over random inputs. Engineers usually quote the worst case, because it is a promise: the algorithm will never do worse, no matter how adversarial the data. Average case matters too, but only if you know the input distribution.

Linear search makes this concrete. To find a target by scanning left to right, the best case is one comparison (it is first), the worst is n (it is last or absent), and the average over random positions is about n/2. Same code, three costs. Choose where the target sits and run it.

Correctness needs its own tool. A loop invariant is a statement that is true before the loop starts and stays true after every iteration. If the invariant holds at the end, and the end condition plus the invariant together imply the answer, the loop is correct. For linear search the invariant is: "the target is not in the part already scanned." When the scan ends, either we found it, or the scanned part is the whole array and it is truly absent. That is a proof, not a hope.

Sorting is the model problem of the field: everyone understands the goal, and the algorithms range from naive to brilliant. We start with the two simplest, both Θ(n²) in the worst case, because seeing why they are slow motivates everything faster.

Bubble sort repeatedly walks the array, swapping any two neighbors that are out of order. Each full pass floats the largest remaining value to its final place, like a bubble rising. Insertion sort instead grows a sorted region on the left: it takes the next item and slides it back until it lands in the right spot, the way you order a hand of cards. Both are real below, animated with live comparison and swap counts. Flip between them on the same array.

Insertion sort has a saving grace: on a nearly sorted array it is close to Θ(n), because each item barely moves. That is why it is used inside faster sorts to clean up small chunks. But in the worst case (a reversed array) both are quadratic, and quadratic is a wall.

The way past the quadratic wall is divide and conquer: split the problem into halves, solve each half, then combine. Merge sort splits the array down to single elements (which are trivially sorted), then merges sorted runs back together. Merging two sorted lists is cheap: walk both with a finger, always taking the smaller front element. Each merge of total length m costs about m comparisons.

There are about log₂ n levels of splitting, and each level does n work to merge everything at that level, so the total is Θ(n log n). The widget runs real merge sort and animates the write-backs as runs combine. Watch the array reassemble in sorted runs of length 1, then 2, then 4.

Quicksort is the other great divide-and-conquer sort, and the one most standard libraries use. Picture sorting a stack of exam papers by picking one paper's score as a splitter: every lower score goes to a left pile, every higher score to a right pile, and that splitter paper is now sitting exactly where it belongs. It picks a pivot, then partitions the array the same way, so everything smaller sits left of the pivot and everything larger sits right. The pivot is now in its final place. Recurse on each pile. No merge step is needed: the partition does the sorting in place.

When pivots split the array roughly evenly, quicksort is Θ(n log n), and its inner loop is so tight it usually beats merge sort in practice. Its dark secret: if pivots are chosen badly (say, always the largest element on an already-sorted array), the split is lopsided and it degrades to Θ(n²). The widget runs the real Lomuto partition and animates the pivot and the scanning pointer.

Merge sort and quicksort both land at n log n. That is not a coincidence, it is a wall. Think of Twenty Questions: every yes/no question can at best cut the remaining possibilities in half, so pinning down one answer among N options takes roughly log₂(N) questions. A comparison sort is playing that same game against the n! possible orderings of the input. Any sort that works only by comparing pairs of elements must make at least Ω(n log n) comparisons in the worst case: each comparison has two outcomes and so at best halves the remaining orderings, and you need enough comparisons to single out the one correct ordering, which takes log₂(n!) ≈ n log₂ n comparisons. No comparison sort can beat it.

Put all four sorts on one starting array and the wall is visible: bubble and insertion pile up quadratic operations while merge and quicksort stay near n log n. Re-roll the array to see the counts hold up across inputs.

Escaping the wall: counting sort

The lower bound only binds comparison sorts. If the keys are small integers, you can sort without ever comparing two of them. Counting sort tallies how many times each value appears, turns those tallies into positions, and drops each element straight into its slot. It runs in Θ(n + k) for values in 0..k, which is linear when k is not much bigger than n. It buys this speed by knowing something extra about the data.

To find a value in an unsorted list you have no choice but to look at everything: linear search, Θ(n). But if the list is sorted, one comparison tells you a great deal. Check the middle element. If your target is smaller, it can only be in the left half; if larger, only the right. Either way, one comparison throws away half the array. That is binary search, and it runs in Θ(log n).

Log growth is staggering. A million sorted items take at most 20 comparisons; a billion take 30. The widget runs real binary search, animating the lo and hi bounds closing in on the target. The greyed cells are the ones proven irrelevant and never examined again.

Ask a friend a question they can't answer outright, and they turn around and ask a second friend a smaller version of the same question, who asks a third, and so on, until someone can answer directly, then the answers travel back up the chain. That line of friends waiting on a reply is the call stack. A recursive function solves a problem by calling itself on smaller inputs, until it hits a base case small enough to answer directly. Merge sort and quicksort are recursive; so is walking a tree. The machine tracks the half-finished calls on the call stack: each call pushes a frame, each return pops one. The stack's depth is the recursion's depth.

The widget traces a real recursive routine (summing an array by repeatedly splitting it in half) and shows the call stack growing as it descends to the base cases, then unwinding as results bubble back up. The tree it draws is the recursion, level by level.

Picture a family tree, or an org chart: the root is the original problem, it spawns a children each holding a piece of size n/b, and each of those spawns its own children, branching downward until the pieces are trivially small. Two costs compete for the total bill: how many leaves pile up at the bottom, and how expensive combining results is at each level on the way back up. Divide-and-conquer algorithms share that exact shape: T(n) = a·T(n/b) + f(n). Solve a subproblems, each of size n/b, and spend f(n) to split and combine. Merge sort is 2·T(n/2) + n. The master theorem reads off the answer by comparing those same two forces: the work that multiplies as you recurse (the leaves, growing like n^(log_b a)) against the work at the top (the root, f(n)).

Whichever force dominates sets the total. If the leaves win, the answer is leaf-heavy. If the root wins, it is root-heavy. If they tie, you pay the tie cost times an extra log n factor (that is where merge sort's log comes from). Slide the parameters and watch which side of the balance tips.

Recursion can be a trap. The naive Fibonacci, fib(n) = fib(n-1) + fib(n-2), looks elegant and is catastrophically slow: it recomputes the same subproblems over and over. fib(5) calls fib(3) twice, fib(2) three times, and the call tree explodes exponentially, about 2ⁿ calls.

The fix is memoization: remember each answer the first time you compute it, and on any later request return the cached value instead of recursing again. The exponential tree collapses to a thin one, because each distinct subproblem is solved exactly once: n+1 of them, so Θ(n). Toggle the cache below and watch the tree shrink and the call count fall off a cliff.

Picture a street grid where you can only walk right or down. The number of ways to reach any corner is simply the ways to reach the corner above it plus the ways to reach the corner to its left: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Edges have one path. Fill the grid corner by corner and the far corner holds the answer.

That is dynamic programming (DP): memoization made deliberate. It applies when a problem has two properties. Optimal substructure: the best solution is built from best solutions to subproblems, exactly as each grid cell is built from the cells above and to its left. Overlapping subproblems: the same subproblems recur, so caching pays off. When both hold, you build a table of subproblem answers from the bottom up, each cell using cells already filled.

The flagship DP is edit distance (Levenshtein): the fewest single-character edits (insert, delete, or substitute) to turn one string into another. It powers spell-checkers, DNA alignment, and diff tools. Turning "kitten" into "sitting" takes 3 edits: substitute k for s, substitute e for i, and insert g; edit distance is the systematic way to find that minimum for any pair of strings, and the widget below finds it for exactly this pair. The subproblem dp[i][j] is the distance between the first i letters of the source and the first j of the target.

The recurrence weighs three moves. If the two current letters match, the cost is whatever dp[i-1][j-1] was, free. Otherwise take 1 + the cheapest of the three neighbors: delete (dp[i-1][j]), insert (dp[i][j-1]), or substitute (dp[i-1][j-1]). The widget fills the real table cell by cell, highlighting the three candidates, then traces the amber path of edits back from the corner.

A graph is nodes joined by edges: road maps, social networks, web links, dependency chains. The two foundational traversals differ only in the order they explore, and that difference comes down to one data structure. Breadth-first search (BFS) uses a queue and explores in rings of increasing distance from the start, so it finds shortest paths in unweighted graphs. Depth-first search (DFS) uses a stack and plunges as deep as it can before backtracking.

The widget runs both on the same graph. Switch modes and watch the frontier: BFS spreads outward evenly, DFS dives down one branch at a time. The numbers on the nodes are the visitation order. Same graph, same start, two very different shapes.

BFS finds shortest paths only when every edge costs the same. Real maps have weights: distances, times, tolls. Dijkstra's algorithm finds the cheapest path from a start to every other node when weights are non-negative. It keeps a tentative distance to each node, always settles the closest unsettled node next (pulled from a priority queue), and relaxes its neighbors: if going through this node is cheaper than their current best, update them.

The genius is the greedy guarantee: once a node is settled, its distance is final and can never improve, because every other route would have to pass through a farther node first. The widget runs real Dijkstra, animating each relaxation and growing the shortest-path tree. The final route to the goal lights up amber.

A greedy algorithm makes the locally best choice at every step and never reconsiders. Greed usually fails to find the global optimum, but for some problems it is provably perfect. The minimum spanning tree (MST) is the classic win: connect every node with the least total edge weight and no cycles, the cheapest possible network that leaves nobody isolated.

Prim's algorithm grows the tree from one node, each step adding the cheapest edge that reaches a node not yet connected. That greedy rule is guaranteed optimal by the cut property: the lightest edge crossing any division of the nodes must belong to some MST. The widget runs real Prim's and highlights each chosen edge in amber as the tree spans the graph.

Every algorithm so far has been efficient: its cost grows as a polynomial in the input size (n, n log n, n²). Call that class P, the problems solvable in polynomial time. But a vast number of important problems have no known polynomial algorithm. The best we have is essentially brute force, and brute force is exponential.

The catch is a strange asymmetry. For many hard problems, checking a proposed answer is easy even though finding one is not. Given a filled-in Sudoku you can verify it in seconds; solving a blank one is another matter. That class, "answers you can verify quickly," is NP. The trillion-dollar question, P vs NP, asks whether fast-to-check always means fast-to-solve. Almost everyone believes no, but nobody has proved it.

Subset sum shows the wall. Given a set of numbers, is there a subset that adds up to a target? Verifying a candidate subset is a single linear pass. Finding one, in general, means checking up to 2ⁿ subsets. Push n and watch the search space detonate while the verifier stays trivial.

Faced with an NP-hard problem in practice, you do not give up, you change the question. Accept a near-optimal answer from an approximation algorithm, use a heuristic that is usually good, or exploit structure special to your inputs. Recognizing that a problem is hard is itself a valuable result: it tells you to stop hunting for a perfect fast algorithm that almost certainly does not exist.

You now have the working vocabulary of algorithms: how to measure cost, the sorting and searching workhorses, recursion and divide-and-conquer, dynamic programming, the graph traversals, and the boundary of what is tractable. The next moves depend on where you want to point it.

The mental shift worth keeping: given any task, ask what the input size is, what growth class you can afford, and which known pattern it matches. That question, asked early, is most of the job.