Algorithms & data structures

The classroom material, shown at sizes the classroom never uses.

9 of 9 topics live on this page

When the data grows

Five common shapes of code, timed as the input grows from 10 items to 10 million. Each line is how long the work takes: the flat ones stay instant forever, the steep ones stop finishing.

Assumes one operation = 10 ns

Input size n

op 10 ns n up to 10M

O(1)
O(log n)
O(n)
O(n log n)
O(n²)

Class	What it looks like in code	Operations	Wall time	Status
O(1)	a hash lookup, an array index	1	10 ns	instant
O(log n)	binary search, a B-tree index probe	3	33.2 ns	instant
O(n)	one pass, a full table scan	10	100 ns	instant
O(n log n)	merge sort, an ORDER BY with an index	33	332 ns	instant
O(n²)	a loop inside a loop, includes() in a map	100	1 µs	instant

Sorting a list, five ways

The same 48 numbers sorted by five methods, running for real side by side. Every lane gets the same number of steps per second, so the method that needs fewer steps finishes first, and the slow ones are still grinding long after the fast ones are done.

Real steps, counted as they happen: comparisons, or digit moves for radix sort, which never compares two numbers

Steps per second

Bubble sort O(n²) 0 comparisons sorting

Insertion sort O(n²) 0 comparisons sorting

Quick sort O(n log n) 0 comparisons sorting

Merge sort O(n log n) 0 comparisons sorting

Radix sort O(n) 0 digit moves sorting

sorting 48 numbers table 1,000,000 step 10 ns

The same five methods on a list of 1,000,000, at 10 ns per step
Method	Steps	Time
Bubble sort	5 × 10¹¹ comparisons	1.39 h
Insertion sort	2.5 × 10¹¹ comparisons	41.7 min
Quick sort	2.77 × 10⁷ comparisons	277 ms
Merge sort	1.99 × 10⁷ comparisons	199 ms
Radix sort	1.4 × 10⁷ digit moves	140 ms

Finding one row

Three ways to find one ID among the same rows, running for real side by side: reading every row in order, binary search over the sorted IDs (what a database index does), and a hash lookup (a Map, or a hash index), each given the same steps per second, so the gap you see is the gap in work.

Real steps, counted as they happen: one row or slot read per step. Hash table at most 50% full, linear probing. The step clock speeds up during each race so the scan can finish.

Rows

Looking for ID 0, a row near the end

Linear scan O(n) 0 steps searching reads rows in order, like array.find

Binary search O(log n) 0 steps searching halves the sorted rows in play, like an index

Hash lookup O(1) 0 steps searching jumps to the slot the ID hashes to, 256 slots

hash fill ≤ 50% step 10 ns

read, in the lane's colour
found
not read yet
ruled out without reading
empty hash slot

Steps to find one row at 10 ns a step. Linear scan and binary search are the worst case; the hash lookup is typical, and averages 1.00 probes on the table above.
Method	1,000 rows	1,000,000 rows	1,000,000,000 rows
Linear scan	1,000 steps 10 µs	1,000,000 steps 10 ms	1,000,000,000 steps 10 s
Binary search	10 steps 100 ns	20 steps 200 ns	30 steps 300 ns
Hash lookup	~1 step ~10 ns	~1 step ~10 ns	~1 step ~10 ns

Checking every order against a blocklist

Two lists of ids, checked for real, one step at a time. Asking an array whether it contains an id walks it from the start, so every order costs a sweep of the blocklist; a Set jumps straight to the one slot where the id would be. Double both lists and the array takes four times as long, the Set twice as long.

Real steps, counted as they happen, with 50% of the orders on the blocklist. Both lanes get the same 100 steps a second. The Set is a hash table kept at most 50% full, probing forward on a collision

Items in each list

Array includes() 0 comparisons checking

for (const id of orderIds) if (blockedIds.includes(id)) hold(id);

Set has() 0 probes checking

const blocked = new Set(blockedIds);
for (const id of orderIds) if (blocked.has(id)) hold(id);

blocked 50% Set fill ≤ 50% speed 100 steps/s step 10 ns

filled order: on the blocklist
outlined order: checked, not blocked
a glowing cell was just compared or probed

The same check on bigger lists, 50% of the orders blocked, at 10 ns per step
Items in each list	includes() comparisons	Time	Set probes	Time
32 (above, on average)	776	7.76 µs	112	1.12 µs
1,000	750,250	7.5 ms	3,500	35 µs
100,000	7.5 × 10⁹	1.25 min	350,000	3.5 ms
1,000,000	7.5 × 10¹¹	2.08 h	3.5 × 10⁶	35 ms

includes() makes about n × n × 0.75 comparisons: a blocked order is found halfway along on average, an unblocked one scans the whole list. The Set costs about 3.5 probes per id, building it included.

Building a string in a loop

Appending pieces to a string one at a time, in a language whose strings cannot change once made (C#, Java). Every s += piece allocates a new string and copies everything built so far into it, so the copying climbs like a staircase; a StringBuilder appends into a buffer that doubles when full, so it only re-copies old bytes at those rare resizes.

Assumes 10-byte pieces (1 byte per character), a builder buffer that starts at 16 bytes and grows 2× when full, one final copy out of the builder, and copying at 10 GB/s

Pieces appended

piece 10 B buffer 16 B grows 2× copy 10 GB/s

solid: the new 10-byte piece
faded: bytes already built, copied again
bar height: bytes copied by that append

100,000 pieces	Bytes copied	Copy time
Concatenation s += piece	50 GB	5 s
StringBuilder sb.Append(piece)	3.05 MB	305 µs

At 100,000 pieces, concatenation copies 16,402× as many bytes as the builder, and every one of those copies is a new string the garbage collector has to clear away. JavaScript engines hide this by keeping += results as ropes (a tree of pieces, flattened once when read), so timing a loop in this browser would not show it; the numbers here come from the model above.

A recursive function with no cache

The textbook recursive Fibonacci, drawn as its call tree while it really runs: with no cache it works out the same small results again and again, so each step up in n costs 1.6 times as many calls, and caching each result (memoisation) folds the whole tree into one line, as it would for any recursive lookup that keeps revisiting the same keys.

Real calls, made and counted as they happen (for n above 30, from the exact closed form 2·fib(n+1) − 1); time assumes 10 ns per call

Which Fibonacci number

Naive 0 of 177 calls

Memoised 0 of 19 calls

call 10 ns

naive, first time a value is computed
naive, repeating a value already computed
memoised call
cache hit, returns at once

Computing fib(10), at 10 ns per call
Version	Calls	Repeats	Time	Status
Naive	177	166	1.77 µs	instant
Memoised	19	8	190 ns	instant

An export job that runs out of memory

A job that writes every order to a CSV file, two ways. One loads the whole table into a list first; the other streams it and holds only one batch of 1,000 rows at a time. Both do the same work in the same time, but the list's memory grows with every row, and past a certain table size the container kills it before it has written a single line.

Assumes 260 B per loaded row (its data plus object overhead), 120 MiB for the runtime, a 512 MiB container limit, 50,000 rows/s read and written, and a restart back-off of 10 s, doubling after each kill up to 5 minutes

Rows to export

Load it all into a list

var orders = await db.Orders
    .AsNoTracking().ToListAsync();
foreach (var o in orders)
    csv.WriteRecord(o);

Stream it in batches of 1,000

await foreach (var batch in db.Orders
    .AsNoTracking().AsAsyncEnumerable()
    .Chunk(1_000))
    csv.WriteRecords(batch);

row 260 B limit 512 MiB runtime 120 MiB batch 1,000 rows speed 50,000 rows/s back-off 10 s

list: memory grows with every row loaded
stream: one batch in memory
OOM kill, then a restart from row 0

In a 512 MiB container the list fits at most 1,580,929 rows. At 2,510,000 rows it would need 742 MiB, so it is killed at row 1,580,930 with nothing written, and every restart dies at the same row. The stream finishes in 1.67 min and never goes above 120 MiB.

Looping over an array vs a linked list

Both loops read every item once, so both are O(n). But the CPU fetches memory from RAM 64 bytes at a time. The array's numbers sit side by side, so one fetch brings in the next eight; the list's nodes are scattered, so nearly every step waits on RAM again. Same big-O, very different constant.

Animation is modelled: 64-byte cache lines, 100 ns per fetch from RAM, 1 ns per read from cache, data far bigger than the cache, no prefetching. The table below is measured for real.

Items to loop over

Array O(n) 8-byte numbers side by side, 8 per cache line 0 / 128 read · 0 RAM fetches · 0 ns reading

Linked list O(n) 16-byte nodes (value + pointer), 4 per line, linked in random order 0 / 128 read · 0 RAM fetches · 0 ns reading

RAM 100 ns cache 1 ns

array: one read after another along memory
linked list: each dashed arc is a jump to the next node
outlined block: one 64-byte cache line, lit while it loads from RAM

Measured in your browser just now: summing numbers from a Float64Array vs from linked node objects, best of 5 runs
Items	Array, per item	Linked list, per item	List is slower by
1,000	measuring…	measuring…	…
100,000	measuring…	measuring…	…
1,000,000	measuring…	measuring…	…

Measuring the real thing in your browser…

Finding duplicate customer emails

Two ways to find the repeats in the same list of emails, running for real side by side. Comparing every email with every later one fills a triangle of comparisons, one cell at a time and row by row; remembering what you have seen in a Set touches each email once, a thin diagonal that is finished before the triangle has got going.

Real loops over a list where about one email in 8 is repeated, counted as they run: each === is one comparison, each Set lookup one lookup. Both get the same steps per second; big-list times at 10 ns per step

Emails in the list

32 × 31 ÷ 2 = 496 comparisons against 32 lookups, at 96 steps per second each

Loop inside a loop comparing 0 / 496 comparisons 0 found

One pass with a Set looking up 0 / 32 lookups 0 found

repeats 1 in 8 speed 3/s per email step 10 ns

// loop inside a loop
for (let i = 0; i < n; i++)
  for (let j = i + 1; j < n; j++)
    if (emails[i] === emails[j]) dupes.push(emails[j]);

// one pass with a Set
const seen = new Set<string>();
for (const email of emails)
  if (seen.has(email)) dupes.push(email);
  else seen.add(email);

one cell per comparison of email i with a later email j
one cell per Set lookup
duplicate found

At real table sizes, 10 ns per step
Emails	Comparisons	Loop time	Lookups	Set time
1,000	499,500	5 ms	1,000	10 µs
100,000	5 × 10⁹	50 s	100,000	1 ms
10,000,000	5 × 10¹³	5.79 days	1 × 10⁷	100 ms