

Algorithms · hands-on The Algorithms Lab You've watched these algorithms run line by line in the traces. Here you grab the controls — change the input, pick the method, press play — and feel in your hands why one approach finishes in a blink and another would still be running tomorrow. Everyone memorises "binary search is O(log n)." Almost no one has felt it. Slide the input size in the first panel and watch the gap between the curves become the gap between instant and never. 🎮 How to use this page Every panel is live — drag the sliders, press Step to move one operation at a time, Play to watch it run. Nothing here is a video: it's the real algorithm executing in your browser. Explore here to build the intuition, then step the matching trace to see one exact run, variable by variable. 01Why speed is the whole game An algorithm's cost isn't a single number — it's a function of how big the input is. Feed it twice the data and a good method barely notices; a bad one takes four times longer, or a thousand. The letter inside `O(…)` names the shape of that function, and at scale the shape is everything. Here's the part that stings: a faster computer only slides a hopeless curve a little to the right — it never changes its shape. The only real fix is a better shape. So we do the one honest thing: count the basic operations as the input `n` grows. Drag `n` below from ten items to a billion and read what each algorithm's operation count becomes — and, at a billion operations per second, how long that actually takes. InteractiveDrag n — watch the curves separate binary search O(log n) linear search O(n) merge sort O(n log n) bubble sort O(n²) input size n = 1,000 Bars are log-scaled so all four fit on one screen — read the numbers on the right for the true gap. Time assumes a billion operations per second. ↺ The thing everyone gets backwards A faster computer does not rescue a bad algorithm. Ten times the speed shifts an `O(n²)` wall ten-fold — the curve still swallows it whole a moment later. Only a better shape — `O(n log n)` instead of `O(n²)` — actually scales. Hardware buys you a constant; the algorithm decides the curve. The deeper cut — where the shapes come from O(log n) is "how many times can you halve n before you hit 1?" — that's log₂. O(n) is "touch each item once." O(n log n) is "do a full pass (n) at each of log n levels" — the merge-sort bill. O(n²) is "for each item, look at every item" — two nested loops. Constants and lower-order terms are dropped because at large n the biggest term drowns them out: at n = 1,000,000, an `n²` term is a trillion while a `100n` term is a hundred million — the `n²` wins by four orders of magnitude, so who cares about the 100. If shape is everything, the biggest win is turning an `O(n)` search into an `O(log n)` one. That trick needs one ingredient — order → 02Order is information — the search race To find one name in a shuffled pile you have to check every card. There's no shortcut, because when the pile is unordered, "close" tells you nothing — the card next to your target looks no different from the one across the room. That's linear search, and its honest cost is O(n): worst case, you look at all of them. Now put the pile in order. Look at the middle card. Too big? The target is in the left half — and you just threw away the entire right half without looking at it. One comparison eliminated not one candidate but half of them. Do it again, and again: that's binary search, and sorted order is the information it spends. Pick a target and race the two methods on the same 15 songs. InteractivePick a target — race linear vs binary Linear search — scans left to right Binary search — halves the window (needs sorted) find linear checks: 0 binary checks: 0 Binary search only works because the row is sorted — that order is the whole trick, and the next panel is how you get it. Binary search's superpower is borrowed: it only works on a sorted list. So the real question becomes — how do you sort one, and why do some ways cost so much more than others? → 03Sorting, in your hands Strip sorting to the metal and it's just two moves: compare two items, and move one. Every sorting algorithm ever invented is a different strategy for spending those two moves — and the only honest way to judge a strategy is to count them. Pick a method, shuffle, and step through it. The amber pair is the comparison happening right now; a red bar just moved; the green region is already sorted and settled. Watch the counters — they never lie. InteractiveSort it yourself — five methods, one array method comparisons: 0 moves: 0 step: 0 / 0 Same starting array, different method: bubble sort re-compares everything (watch its counter balloon); merge sort splits the work in half at each level and its counter stays small. ✗ The myth The "best" sort is the cleverest, fanciest one, always. ✓ The reality For a tiny or nearly-sorted array, plain insertion sort beats them all — no recursion, no overhead. Python's own `sorted()` (Timsort) is a hybrid that literally falls back to insertion sort on small runs. Match the method to the data. 🧠 The five, in one line each Bubble: swap adjacent out-of-order pairs; the biggest floats to the end each pass. Selection: find the smallest, swap it to the front; one move per pass. Insertion: slide each item back into the sorted part, like a hand of cards. Merge: split in half, sort each, merge the two sorted halves. Quick: pick a pivot, shove smaller left and bigger right, recurse. Merge and quicksort both win by splitting the problem in half and recursing. But recursion has a dark side that can turn elegant code into a machine that never finishes → 04The exponential trap — and the cache that springs it Recursion is a function calling itself on a smaller version of the problem. It's beautiful — and it can be a disaster. Naive Fibonacci says `fib(n) = fib(n-1) + fib(n-2)`: to get one answer it asks two questions, each of which asks two more. The same tiny sub-problems get re-solved over and over — the whole left side of the tree recomputes work the right side already did. Drag `n` and watch the call count explode. Then flip to memoised. The rule is one word longer: the first time we solve a given `fib`, we write the answer down; every later request for it is a single lookup instead of a whole sub-tree. The branches collapse into cache hits. Exponential becomes linear — from the same code, plus a dict. InteractiveDrag n — watch the tree explode, then collapse n = 5 naive recursion memoised (with a cache) fib(n) = 5 naive calls: 15 memoised calls: 9 The tree is drawn for n ≤ 6 (beyond that it has too many nodes to fit — which is exactly the point). In memo mode, a green node is a cache hit: solved once, never expanded again. 💡 You've seen this before That cache is `functools.lru_cache` from Volume 1 — memoisation is the whole idea, built by hand. Writing answers down is the difference between `2ⁿ` and `n`: for `fib(50)`, that's about 25 billion calls versus fifty. Same code, one dict, an astronomically different bill. That "remember what you've already worked out" move is one of a handful of patterns that separate brute force from elegance → 05Two ways to learn each of these You now have both halves of understanding an algorithm, side by side. This lab lets you explore — change the input, pick the method, and see the whole run at a glance until the intuition clicks. The trace walkthroughs let you step — one exact run, every variable and every stack frame drawn at each beat. Part D of the traces covers all twelve of these algorithms line by line; this page is where you first feel them move. ✅ The move that follows from all of this When you meet a new algorithm, don't memorise its Big-O — derive it. Count the comparisons and moves as the input grows, and the letter in `O(…)` falls out on its own. That's the whole skill, and now you can watch it happen. Next in the series: the thirteen must-know data structures — linked list, stack, queue, tree, heap, graph and the rest — each built from scratch and stepped through the same engine, with the `curr` pointer walking the list and `find(4)` climbing the union-find tree in front of you. On this page 01 · Why speed is the whole game 02 · The search race 03 · Sorting, in your hands 04 · The exponential trap 05 · Two ways to learn

Algorithms · hands-on

The Algorithms Lab

You've watched these algorithms run line by line in the traces. Here you grab the controls — change the input, pick the method, press play — and feel in your hands why one approach finishes in a blink and another would still be running tomorrow.

Everyone memorises "binary search is O(log n)." Almost no one has felt it. Slide the input size in the first panel and watch the gap between the curves become the gap between instant and never.

🎮

How to use this page

Every panel is live — drag the sliders, press Step to move one operation at a time, Play to watch it run. Nothing here is a video: it's the real algorithm executing in your browser. Explore here to build the intuition, then step the matching trace to see one exact run, variable by variable.

01Why speed is the whole game

An algorithm's cost isn't a single number — it's a function of how big the input is. Feed it twice the data and a good method barely notices; a bad one takes four times longer, or a thousand. The letter inside O(…) names the shape of that function, and at scale the shape is everything. Here's the part that stings: a faster computer only slides a hopeless curve a little to the right — it never changes its shape. The only real fix is a better shape.

So we do the one honest thing: count the basic operations as the input n grows. Drag n below from ten items to a billion and read what each algorithm's operation count becomes — and, at a billion operations per second, how long that actually takes.

InteractiveDrag n — watch the curves separate

binary search
O(log n)

linear search
O(n)

merge sort
O(n log n)

bubble sort
O(n²)

input size n = 1,000

Bars are log-scaled so all four fit on one screen — read the numbers on the right for the true gap. Time assumes a billion operations per second.

↺ The thing everyone gets backwards

A faster computer does not rescue a bad algorithm. Ten times the speed shifts an O(n²) wall ten-fold — the curve still swallows it whole a moment later. Only a better shape — O(n log n) instead of O(n²) — actually scales. Hardware buys you a constant; the algorithm decides the curve.

The deeper cut — where the shapes come from

O(log n) is "how many times can you halve n before you hit 1?" — that's log₂. O(n) is "touch each item once." O(n log n) is "do a full pass (n) at each of log n levels" — the merge-sort bill. O(n²) is "for each item, look at every item" — two nested loops. Constants and lower-order terms are dropped because at large n the biggest term drowns them out: at n = 1,000,000, an n² term is a trillion while a 100n term is a hundred million — the n² wins by four orders of magnitude, so who cares about the 100.

If shape is everything, the biggest win is turning an O(n) search into an O(log n) one. That trick needs one ingredient — order →

02Order is information — the search race

To find one name in a shuffled pile you have to check every card. There's no shortcut, because when the pile is unordered, "close" tells you nothing — the card next to your target looks no different from the one across the room. That's linear search, and its honest cost is O(n): worst case, you look at all of them.

Now put the pile in order. Look at the middle card. Too big? The target is in the left half — and you just threw away the entire right half without looking at it. One comparison eliminated not one candidate but half of them. Do it again, and again: that's binary search, and sorted order is the information it spends. Pick a target and race the two methods on the same 15 songs.

InteractivePick a target — race linear vs binary

Linear search — scans left to right

Binary search — halves the window (needs sorted)

find

linear checks: 0 binary checks: 0

Binary search only works because the row is sorted — that order is the whole trick, and the next panel is how you get it.

Binary search's superpower is borrowed: it only works on a sorted list. So the real question becomes — how do you sort one, and why do some ways cost so much more than others? →

03Sorting, in your hands

Strip sorting to the metal and it's just two moves: compare two items, and move one. Every sorting algorithm ever invented is a different strategy for spending those two moves — and the only honest way to judge a strategy is to count them. Pick a method, shuffle, and step through it. The amber pair is the comparison happening right now; a red bar just moved; the green region is already sorted and settled. Watch the counters — they never lie.

InteractiveSort it yourself — five methods, one array

method

comparisons: 0 moves: 0 step: 0 / 0

Same starting array, different method: bubble sort re-compares everything (watch its counter balloon); merge sort splits the work in half at each level and its counter stays small.

✗ The myth

The "best" sort is the cleverest, fanciest one, always.

✓ The reality

For a tiny or nearly-sorted array, plain insertion sort beats them all — no recursion, no overhead. Python's own sorted() (Timsort) is a hybrid that literally falls back to insertion sort on small runs. Match the method to the data.

🧠

The five, in one line each

Bubble: swap adjacent out-of-order pairs; the biggest floats to the end each pass. Selection: find the smallest, swap it to the front; one move per pass. Insertion: slide each item back into the sorted part, like a hand of cards. Merge: split in half, sort each, merge the two sorted halves. Quick: pick a pivot, shove smaller left and bigger right, recurse.

Merge and quicksort both win by splitting the problem in half and recursing. But recursion has a dark side that can turn elegant code into a machine that never finishes →

04The exponential trap — and the cache that springs it

Recursion is a function calling itself on a smaller version of the problem. It's beautiful — and it can be a disaster. Naive Fibonacci says fib(n) = fib(n-1) + fib(n-2): to get one answer it asks two questions, each of which asks two more. The same tiny sub-problems get re-solved over and over — the whole left side of the tree recomputes work the right side already did. Drag n and watch the call count explode.

Then flip to memoised. The rule is one word longer: the first time we solve a given fib, we write the answer down; every later request for it is a single lookup instead of a whole sub-tree. The branches collapse into cache hits. Exponential becomes linear — from the same code, plus a dict.

InteractiveDrag n — watch the tree explode, then collapse

n = 5

naive recursion memoised (with a cache)

fib(n) = 5 naive calls: 15 memoised calls: 9

The tree is drawn for n ≤ 6 (beyond that it has too many nodes to fit — which is exactly the point). In memo mode, a green node is a cache hit: solved once, never expanded again.

💡

You've seen this before

That cache is functools.lru_cache from Volume 1 — memoisation is the whole idea, built by hand. Writing answers down is the difference between 2ⁿ and n: for fib(50), that's about 25 billion calls versus fifty.

Same code, one dict, an astronomically different bill. That "remember what you've already worked out" move is one of a handful of patterns that separate brute force from elegance →

05Two ways to learn each of these

You now have both halves of understanding an algorithm, side by side. This lab lets you explore — change the input, pick the method, and see the whole run at a glance until the intuition clicks. The trace walkthroughs let you step — one exact run, every variable and every stack frame drawn at each beat. Part D of the traces covers all twelve of these algorithms line by line; this page is where you first feel them move.

✅

The move that follows from all of this

When you meet a new algorithm, don't memorise its Big-O — derive it. Count the comparisons and moves as the input grows, and the letter in O(…) falls out on its own. That's the whole skill, and now you can watch it happen.

Next in the series: the thirteen must-know data structures — linked list, stack, queue, tree, heap, graph and the rest — each built from scratch and stepped through the same engine, with the curr pointer walking the list and find(4) climbing the union-find tree in front of you.