Episode 11 · Ten times the hotels

Big O intuition: how code slows down as data grows

Monday, 10:05: a hotel chain wants to bring its 10,800 hotels to StayHub, in waves from next month: ten times the 1,200 we have. Karim needs to know by Friday what breaks, and the data to test with doesn't exist yet.

No maths anxiety needed. Big O is just a way to ask: when the data grows 10 times, how much more work does my code do?

30 min foundationBig-O intuition: O(n) vs O(log n)Complexity classes: O(1), O(log n), O(n), O(n log n), O(n²)Accidental O(n²): nested loops over growing dataDatabase indexesScalability

Problem
Code that answers in 5 ms on 1,000 test records takes 3 hours on 1,000,000 production records.
Why the simple system fails
Benchmarks on small data hide how work grows. A nested loop is invisible at n = 100 and catastrophic at n = 100,000.
Engineering concept
Big O describes how the number of steps grows with input size n, ignoring constants: O(1), O(log n), O(n), O(n log n), O(n²).
Technology
Hash maps for O(1) lookups, sorting plus binary search and database B-tree indexes for O(log n), Sets instead of nested loops.
Trade-offs
Faster lookups cost memory and slower writes (indexes, sorted data). Constants still matter for small n, so measure before optimising.

The problem

2 min

Monday, 10:05. Karim has news from sales.

Karim · CTO
A chain wants to bring its 10,800 hotels, in waves from next month. We have 1,200. What breaks? Answer by Friday.
You · Engineer at StayHub
We can't load-test with hotels we don't have yet.
Lina · Senior engineer, your mentor
We can reason. The nightly duplicate check compares every hotel with every other. Guess how it grows.

The big idea

4 min

What happens at 10× the hotels?

The big idea

Big O tells you how work grows when the data grows, not how many milliseconds it takes.

So you can answer Karim on Monday, without test data: for each piece of code, ask "10× the data, how much more work?"

How it works

5 min

n is the size of the input: hotels, bookings, rows. describes the shape of the growth as n grows. It ignores whether a step takes 1 µs or 5 µs.

Five shapes, from flat to steep

1
O(1), constant
Same work at any size. A lookup by id: 1,200 or 12,000 hotels, one step.
2
O(log n)
Halve what's left each step: , a database . 1,200 → about 10 steps; 12,000 → about 14; 1,000,000 → about 20.
3
O(n), linear
Touch every item once: a scan, a sum, a . 10× data, 10× work.
4
O(n log n)
The cost of a good sort. A bit more than linear; fine for millions.
5
O(n²), quadratic
Every pair: nested loops, or a find inside a loop. 10× data, 100× work.

The duplicate check: 1,200 × 1,200 ÷ 2 = 720,000 pairs at about 55 µs each: 40 s. At 12,000: 72 million pairs, about 67 minutes. The ÷ 2 and the 55 µs set the exact time; the shape decides whether 10× data means 1×, 10× or 100× the work.

Watch a decision being made

4 min

Worked example

Auditing StayHub for 10× the hotels

From 1,200 to 12,000 hotels, without test data. Find which code paths break and fix the worst one.

1List the paths, find n and the shape
Hotel page by id (Map): O(1). Search (indexed): O(log n). Nearby-hotels widget, scanning all hotels per view: O(n). Nightly duplicate check: O(n²).
Why: The shape, not today's speed, tells you what happens at 10×.
2Multiply by the growth
Page 1 → 1 step; search ~10 → ~14; nearby 4 → 40 ms per view; duplicates 40 s → about 67 min.
Why: "It's O(n²)" means nothing to the business; "67 minutes every night" does.

3Fix the steepest curve

Hotels at different postcodes can't be duplicates. Group by postcode in one pass, compare pairs only inside each group.

const byPostcode = new Map<string, Hotel[]>();
for (const h of hotels) {                        // O(n): one pass
  const list = byPostcode.get(h.postcode) ?? [];
  list.push(h);
  byPostcode.set(h.postcode, list);
}
for (const group of byPostcode.values()) comparePairs(group); // small groups

Why: You need fewer comparisons, not faster ones. Groups of ~20 drop 72 million pairs to under a million.

4Watch, don't fix, the linear one
Nearby at 40 ms per view is acceptable. Note it, with the n where it will hurt.
Why: Fix what breaks; write down what breaks next.

In real life

3 min

"Find this text": opposite choices

ripgrep / grep: scan every time

Reads every file on each search: O(n)
No index to build; always sees the latest files
Fine for one project, too slow for all of GitHub

Right when n is small enough to scan in a moment.

GitHub code search: build an index

Has publicly described building its own search index for code
Each search looks up the index instead of reading every file
Cost: the index is rebuilt as code changes

Right when n is enormous and searches are constant.

What goes wrong

3 min

Testing only on small data

At n = 100, O(n²) and O(n) look the same.

Instead

Test with production-sized data, or reason about 10× and 100×.

A scan inside a loop (`includes`, `find`, `some`)

Each call is O(n), so the loop is O(n²) with no visible nested for.

Instead

Build a Set or Map once before the loop.

Thinking O(1) always beats O(n)

Big O hides constants: scanning 8 currency codes can beat hashing.

Instead

For small, capped n, keep the simplest code.

Trade-offs

3 min

Option	Fits when	You pay	Main risk
Scan, O(n)	Small or capped n, rare runs	Nothing up front	Grows with the data
Index, O(log n)	Frequent lookups on large, growing data	Slower writes, storage	Helps only the indexed key
Hash map, O(1)	Many exact-key lookups in memory	Memory for the whole map	No ranges; must stay in sync

Wednesday, 15:00. Two days before Karim's deadline.

Karim · CTO
Move the duplicate check to a server with 4× the cores. Today, no code changes.
Lina · Senior engineer, your mentor
That's about 17 minutes. The next chain puts us back. Grouping by postcode takes a day and fixes the shape.
Karim · CTO
A day not spent on the chain's onboarding. And grouping might miss duplicates with a postcode typo.

Your job as tech lead

4 min

Claude Code can write the code for this. You still own the decisions, and you have to know what good looks like to accept or reject its work.

Decisions you own

The size you design for: 12,000 hotels after the chain deal, not today's 1,200.
Which paths are hot (every hotel-page view) and deserve attention, and which are small and bounded (8 currency codes) and stay simple.
Whether the database does the filtering, with an index, instead of loading 1.2 million bookings into the app.

Tell Claude Code

A chain is taking StayHub from 1,200 to 12,000 hotels. Before we import them, audit four paths and give each its Big O and estimated time today and at 12,000: hotel page by id, search by city and price, the "Nearby hotels" widget, and the nightly duplicate check comparing every pair. Don't change code yet. For anything worse than 10× slower at 10× data, propose a fix and its cost (memory, an index, precision). Show the arithmetic, not just labels.

Check before you accept

The pairwise check is 720,000 pairs today and 72M at 12,000: 100× the time, not 10×.
Claude points at the exact line that makes a path O(n) or O(n²), like a find inside a loop.
Timings use 12,000 generated hotels on staging, not the 50 in test fixtures.

Red flags

It optimises a path that's already O(1) and leaves the O(n²) job alone.
A bigger server for work that grows 100× when data grows 10×.
It replaces map with a for loop and calls it a complexity fix.

Check yourself

2 min

Q1/3Reasoning

A nested-loop duplicate check takes 2 seconds on 10,000 guests. Roughly how long will it take on 100,000 guests, in seconds?

How confident are you?

Next episode: the chain's first 300 hotels are in, and their hotel pages wait on three services one after another. Guests stare at a spinner for 2.4 seconds.

Finished?

Mark it complete to update your skill map.

Next: Async and concurrency: doing many things while waiting

Go deeper (optional)You don't need this to understand the lesson. Open it when a project needs the details: Technical deep dive, Interactive simulation, Visual diagram, Analogy, Check your understanding, Practice ladder, Explain it yourself.

Technical deep dive

Auditing four code paths

Lina's audit method fits on a sticky note: list the paths, find n, find the shape, multiply, fix the steepest. This time you estimate first and Lina checks.

Worked example

Auditing StayHub for 10× the hotels

The chain would bring StayHub from 1,200 to 12,000 hotels, in waves from next month. Without test data, find which code paths break and fix the worst one.

1List the paths that touch hotels
Hotel page by id (a Map), search by city and price (indexed query), the nearby-hotels widget (scans all hotels per page view), the nightly duplicate check (every pair).
Why: You can only estimate code you've named. Paths that run per request matter more than paths that run once a night.
2Find n and the shape of each
Map lookup: O(1). Indexed search: O(log n). Nearby: O(n) per view. Duplicates: O(n²) per night.
Why: The shape, not today's speed, tells you what happens at 10×. A path that's fast today can be the steepest curve.
3Multiply by the growth
At 10× hotels: page 1 step → 1 step; search ~10 → ~14 steps; nearby 4 ms → 40 ms per view; duplicates 40 s → about 67 min.
Why: Turning shapes into numbers lets Karim decide. "It's O(n²)" means nothing to the business; "67 minutes every night, competing with the other nightly jobs for the database" does.

4Fix the steepest curve

Two hotels at different postcodes can't be duplicates. Group by postcode in one pass, then compare pairs only inside each group.

const byPostcode = new Map<string, Hotel[]>();
for (const h of hotels) {                        // O(n): one pass
  const list = byPostcode.get(h.postcode) ?? [];
  list.push(h);
  byPostcode.set(h.postcode, list);
}
for (const group of byPostcode.values()) comparePairs(group); // small groups

Why: You don't need a faster comparison; you need fewer comparisons. With groups of ~20 hotels, pairs drop from 72 million to well under a million.

5Decide what to watch, not fix
Nearby at 40 ms per view is acceptable today. Note it, and plan a geo index if hotels grow 10× again.
Why: Not every linear path needs work now. Fix what breaks; write down what will break next, with the n where it will.

// Hidden O(n × m): includes is a scan, inside a loop.
bookings.map((b) => ({ ...b, vip: vipEmails.includes(b.email) }));

// O(n + m): build a Set once, then each check is one step.
const vips = new Set(vipEmails);
bookings.map((b) => ({ ...b, vip: vips.has(b.email) }));

The most common accidental O(n²): `includes`, `find`, `some` or a query inside a loop.

Shape	n = 1,000	n = 1,000,000	Typical example
O(1)	1 step	1 step	Map get, array[i]
O(log n)	~10	~20	Binary search, B-tree index
O(n)	1,000 (~10 µs)	1M (~10 ms)	Scan, sum, full table scan
O(n log n)	~10k (~0.1 ms)	~20M (~0.2 s)	Sorting
O(n²)	1M (~10 ms)	10¹² (~3 hours)	Nested loops, every pair

Illustrative times at ~10 ns per in-memory step. Disk and network steps are far slower, which widens every gap.

Interactive simulation

Visual diagram

Guest

Booking API

Unsorted list (1M)

Sorted by email

Hash map email → id

PostgreSQL + B-tree index

Click a component

Three ways to answer "find booking for guest@example.com" among 1,000,000 bookings (roughly StayHub's size today: ~1.2M and growing). Start the walkthrough.

Analogy

Finding a guest at a hotelGrowth shape

Finding a guest at a hotelGrabbing hook 412 from the key rackGrowth shapeFlat: O(1)
Finding a guest at a hotelFlipping an alphabetical register in halvesGrowth shapeHalving: O(log n)
Finding a guest at a hotelReading a messy pile of cardsGrowth shapeStraight line: O(n)
Finding a guest at a hotelSorting the pile into a register firstGrowth shapeSorting: O(n log n)
Finding a guest at a hotelComparing every card with every otherGrowth shapeExplodes: O(n²)

Where the analogy breaks: a person gets tired, a computer doesn't. But a computer meets millions of cards, where the shape of growth matters far more than how fast each single step is.

Check your understanding

Q1/4Reasoning

About how many comparisons does binary search need, in the worst case, to find a record among 1,000,000 sorted records?

comparisons

How confident are you?

Practice ladder

Step 1 · Trace

Trace the growth of three functions

Estimation Warm-up

Three functions run on StayHub's 1.2 million bookings:

// A
const total = bookings.reduce((s, b) => s + b.priceCents, 0);

// B
const guest = bookingsByEmail.get(email);            // a Map

// C
const repeat = bookings.filter((b) =>
  bookings.some((o) => o.guestEmail === b.guestEmail && o.id !== b.id));

For each, give its shape, and say how its work changes when bookings grow from 1.2 million to 2.4 million.

Step 2 · Complete

Finish Lina's estimate table

Estimation Practice

Lina's audit table for the chain (1,200 → 12,000 hotels) has two empty cells. Fill them in, with a one-line reason for each.

Path	Shape	Today	At 12,000 hotels
Hotel page (Map by id)	O(1)	1 ms	1 ms
Sitemap generation (sort hotels by name once a day)	O(n log n)	0.5 s	___
Photo check (for each hotel, look up its photos in an array of all photos with `filter`)	___	20 s	2,000 s (~33 min)

Step 3 · Solve

The owner report that times out

Debugging Practice

The monthly owner report shows, for each hotel, its bookings and its reviews. It worked for 1,200 hotels; on staging with the chain's 12,000 it times out after 30 s.

for (const hotel of hotels) {                                  // 12,000
  const b = await db.query("SELECT * FROM bookings WHERE hotel_id = $1", [hotel.id]);
  const r = reviews.filter((x) => x.hotelId === hotel.id);     // 300,000 reviews in memory
  report.push({ hotel, bookings: b.rows, reviews: r });
}

bookings.hotel_id has no index. Find every growth problem in this loop and fix them.

Step 4 · Decide

Optimise the currency list?

Decision Stretch

In code review, a teammate flags this on the checkout page:

const SUPPORTED = ["EUR", "GBP", "USD", "CHF", "JPY", "SEK", "NOK", "DKK"];
if (!SUPPORTED.includes(req.currency)) return badRequest("unsupported currency");

"includes is O(n)! Use a Set." Karim asks you to decide. Write it as "We chose X over Y because…, accepting the risk of…", and say when you'd change your mind.

Explain it yourself

Explain to a junior teammate why finding a booking by email among 1,000,000 rows can take 20 steps or 1,000,000 steps, and what decides which one you get.

0 words