Building Software
Sections

Contents Section 4, Math and Algorithms

Algorithms, Data Structures and Complexity

How the choice of algorithm and data structure decides whether code scales, and how to read that from the code before it meets real data.

Section 4 of 9, subsection 2 of 4. Depth: do. Core 10 of 25. An 8-minute read.

Mistakes to catch in review

  1. A nested loop over two lists, taking quadratic time, where a hash map lookup would make it linear.

  2. A linear search or list-membership check inside a loop that looks harmless and dominates run time at scale.

  3. The same expensive value recomputed on every iteration or every request instead of once.

Reading Run Time Off the Page

You ask an agent to attach the customer's name to each order before an export. It writes this, and the tests pass:

TypeScript
function attachNamesScan(orders, customers) {
  const result = [];
  for (const order of orders) {
    for (const customer of customers) {
      if (customer.id === order.customerId) {
        result.push({ ...order, customerName: customer.name });
        break;
      }
    }
  }
  return result;
}

The test fixture had 20 orders and 10 customers, and the function returned in well under a millisecond. In production the export has 100,000 orders and 100,000 customers. Measured under Bun on a laptop, this function, which this lesson calls attachNamesScan, takes about 7.4 seconds. A version that does the same job with a different data structure, attachNamesMap below, takes about 12 milliseconds, roughly six hundred times faster, and the gap keeps widening as the data grows.

The code has no sleep and no network call, and each line looks cheap. The cost is in the shape: a loop inside a loop. You can read that shape off the page and put a number on it before the code meets real data.

Count the steps, then ignore the constants

A computer runs code as a sequence of basic steps: compare two numbers, read a field, add to an array. Each takes from a fraction of a nanosecond to a few nanoseconds when the data is in the CPU cache, and much longer when it is not, or when it allocates memory. What decides whether a function is fast is how many steps it takes, and in particular how that count grows as the input grows.

An outer box, Each order, runs n times. Inside it sits the inner loop: Scan customers until the id matches, which takes about m/2 comparisons, or a full m when the customer is missing. That per-order cost, times n, gives the total n × m / 2, 5 billion at 100,000 each.
Every order scans the customer list until the id matches, about m/2 comparisons. Multiply by n orders and 100,000 of each gives 5 billion.

Count the steps in attachNamesScan. The outer loop runs once per order, call that n. For each order, the inner loop scans customers until it finds a match. With m customers and a random match position, that is about m/2 comparisons on average, and a full m when the customer is missing. Total work is about n × m / 2 comparisons. With 100,000 of each, that is 5 billion.

Big-O notation keeps the growth and drops the constant. n × m / 2 is O(n × m), and when both lists are about the same size it is O(n²), called quadratic. The constant matters for the exact time, but it never changes the shape: double the input to a quadratic function and the work goes up four times, multiply it by ten and the work goes up a hundred times.

Here is what the common growth rates mean in raw step counts:

n O(n) O(n log n) O(n²)
1,000 1,000 about 10,000 1,000,000
100,000 100,000 about 1.7 million 10 billion
10,000,000 10 million about 230 million 100 trillion

As a rough working figure, a JIT-compiled or compiled language does a few hundred million to a billion simple steps per second, and a plain CPython loop does tens of millions. So a quadratic loop is harmless at a thousand items, costs seconds to minutes at a hundred thousand, and does not finish in any useful time at ten million. A linear loop is fine at all three. That is how a quadratic function passes a test suite built from small fixtures and then fails on production data.

The rewrite: trade a scan for a lookup

The inner loop exists to answer one question: which customer has this id? Scanning a list answers it in O(m). A hash map answers it in O(1) on average, meaning the time for one lookup stays about the same however many entries the map holds. It does this by computing a number from the key and using it to jump straight to the right bucket.

So build the map once, then look up each order:

TypeScript
function attachNamesMap(orders, customers) {
  const nameById = new Map();
  for (const c of customers) {
    if (!nameById.has(c.id)) nameById.set(c.id, c.name);
  }
  const result = [];
  for (const order of orders) {
    if (nameById.has(order.customerId)) {
      result.push({ ...order, customerName: nameById.get(order.customerId) });
    }
  }
  return result;
}

Building the map is O(m). The second loop is O(n) with constant-time lookups inside. The total is O(n + m), linear. The cost is space: the map holds one entry per customer, so memory use is O(m) where the old version used none beyond the result.

Customers, m of them, go into Build the map, which runs once and first fills the nameById map with one entry per customer. Then orders, n of them, go into Look up each, which reads that map by customer id at O(1) on average. Both passes lead to the total, O(n + m): the build adds O(m), the lookups add O(n), and the map costs O(m) memory.
The map is built once from the customers, and each order then makes one lookup in it. The two passes run one after the other, so their costs add to O(n + m) instead of multiplying.

You can check that arithmetic by counting. The playground below gives both functions a step counter: one step per comparison in the scan, and one per map insert or lookup in the rewrite. Every order points at a different customer, spread through the list.

TypeScriptRuns in your browser
type Customer = { id: number; name: string };
type Order = { id: number; customerId: number };
let steps = 0;

function attachNamesScan(orders: Order[], customers: Customer[]) {
  const result = [];
  for (const order of orders) {
    for (const customer of customers) {
      steps++;
      if (customer.id === order.customerId) {
        result.push({ ...order, customerName: customer.name });
        break;
      }
    }
  }
  return result;
}

function attachNamesMap(orders: Order[], customers: Customer[]) {
  const nameById = new Map<number, string>();
  for (const c of customers) {
    steps++;
    if (!nameById.has(c.id)) nameById.set(c.id, c.name);
  }
  const result = [];
  for (const order of orders) {
    steps++;
    if (nameById.has(order.customerId)) {
      result.push({ ...order, customerName: nameById.get(order.customerId)! });
    }
  }
  return result;
}

for (const fn of [attachNamesScan, attachNamesMap]) {
  for (const n of [1_000, 10_000]) {
    const customers = Array.from({ length: n }, (_, i) => ({ id: i, name: `customer ${i}` }));
    const orders = Array.from({ length: n }, (_, i) => ({ id: i, customerId: (i * 7919) % n }));
    steps = 0;
    fn(orders, customers);
    console.log(fn.name, n, "items:", steps, "steps");
  }
}

Ten times as many items gives the scan about 100 times as many steps, 50,005,000 against 500,500, and the map version exactly 10 times as many. The counts are the same on every machine and every run, which makes them a cleaner first check than a stopwatch.

Three details keep the rewrite honest. The original skipped orders whose customer was missing, so the new version does too. The original took the first matching customer when ids repeated, so the map keeps the first one it sees. The third is an assumption: ids are strings or integers, validated where the data enters the system. A Map treats NaN as equal to NaN and === never does, so an order whose customer id is NaN gets a name from the map version and is skipped by the scan. A rewrite for speed that silently changes which rows come out is a new bug. When you ask an agent for the faster version, ask it which inputs, if any, produce different output.

Where else quadratic time hides

A search can also hide inside a method call. These lines each contain a loop:

TypeScript
const active = users.filter((u) => !bannedIds.includes(u.id));
const idx = rows.findIndex((r) => r.sku === sku);

Array.prototype.includes, indexOf, find and findIndex scan the array from the start. So does x in some_list in Python, which the Python wiki's TimeComplexity page lists as O(n), against O(1) on average for a set. The first line above is a loop over users with a scan of bannedIds inside each step, so it is O(users × banned). The fix is to build new Set(bannedIds) once and call .has(). The question to ask of every method call inside a loop is: does this method walk a collection?

Recomputation is the other place. A value that does not change between iterations gets recomputed on every one:

TypeScript
const maxScore = (rs) => rs.reduce((m, x) => Math.max(m, x.score), -Infinity);
const top = rows.filter((r) => r.score >= 0.9 * maxScore(rows));

The maximum is the same for every row, but the code computes it n times, each time over all n rows. That is O(n²) for what should be O(n). Compute maxScore(rows) once into a variable above the filter and the scan runs once. The same pattern appears across requests: a handler that reads and parses a config file, compiles a regular expression, or builds a lookup table from the whole database on every request. For each expensive expression inside a loop or a handler, ask what it depends on. If nothing it depends on changes from one iteration or request to the next, compute it once outside.

Choosing a data structure from the access pattern

Every data structure makes some operations cheap by making others expensive. You choose one by writing down what the code will do most often, then picking the structure that makes that operation cheap.

Structure Cheap Expensive
Array or list read by position, append at the end find by value O(n), insert or remove at the front O(n)
Hash map or set insert, delete, look up by key, O(1) average anything that needs order, such as "all keys between A and F"
Sorted tree (and B-tree database indexes) look up and insert in O(log n); a range query returning k entries in O(log n + k), in order a lookup makes O(log n) comparisons where a hash map averages O(1) key checks; real speed depends on memory layout and cache
Heap (priority queue) read the smallest item O(1), add or remove O(log n) find an arbitrary item O(n)
Queue or deque add and remove at either end O(1) find by value O(n)

Read a described access pattern into a row of that table. "Look up a user by email on every request" is a hash map. "Show all orders placed between two dates" wants order, so a sorted structure or a database index on the date. "Always run the most urgent job next" is a heap. "Process jobs in the order they arrived" is a queue, and in Python that means collections.deque, because list.pop(0) shifts every remaining element and costs O(n).

Predict, then measure

A complexity class makes a prediction you can test. If a function is linear, ten times the input should take about ten times as long. If it is quadratic, about a hundred times. Measuring both versions at three sizes gave this, in one run under Bun on a laptop:

n (orders = customers) nested loop map lookup
1,000 2.8 ms 0.4 ms
10,000 73 ms 1.0 ms
100,000 7,385 ms 11.9 ms

From 10,000 to 100,000 the nested loop took about 100 times longer and the map version about 12 times longer, which is what the two growth rates predict. The step from 1,000 to 10,000 does not match as well, because at a few milliseconds the timer, the JIT compiler warming up and memory allocation are a large share of the total. Measure at sizes where each run takes at least tens of milliseconds, and compare the ratios between sizes.

The measuring code is short. makeInput gives every customer a distinct id and every order a random customer, so the scan has to walk half the list on average, as the step count assumed:

TypeScript
function makeInput(n) {
  const customers = Array.from({ length: n }, (_, i) => ({ id: i, name: `customer ${i}` }));
  const orders = Array.from({ length: n }, (_, i) => ({
    id: i,
    customerId: Math.floor(Math.random() * n),
  }));
  return [orders, customers];
}

for (const fn of [attachNamesScan, attachNamesMap]) {
  for (const n of [1_000, 10_000, 100_000]) {
    const [orders, customers] = makeInput(n);
    const start = performance.now();
    fn(orders, customers);
    console.log(fn.name, n, (performance.now() - start).toFixed(1), "ms");
  }
}

Write your prediction down before you run it. If the ratio is far off, either your reading of the code is wrong or something else, like a hidden scan in a library call, is doing work you did not count.

The same ratio lets you extrapolate from a test. If a quadratic function takes 2 milliseconds on 1,000 items, it takes about 2 × 100² = 20,000 milliseconds, or 20 seconds, on 100,000.

Constant factors and repeated subproblems

Big-O describes growth and hides constant factors, and at small sizes the constants win. Scanning an array of eight items can be faster than hashing a key, because the array sits in one contiguous block of memory and the CPU reads it quickly. The standard library's comparison sorts are O(n log n) comparisons, each costing whatever your comparator costs, and they are heavily tuned, so calling the built-in is almost always better than an agent's hand-written sort. The Big-O class tells you which version will lose as data grows. For which one is faster at the size you actually have, measure.

Recursion has its own trap. A recursive function that calls itself twice on overlapping subproblems can take exponential time:

TypeScript
function ways(n) {
  if (n <= 1) return 1;
  return ways(n - 1) + ways(n - 2);
}

ways(40) makes over 300 million calls because it solves the same smaller cases again and again. Storing each answer the first time it is computed, in a map keyed on n, makes it linear. That technique is dynamic programming. The sign to look for is a recursive call tree where the same arguments appear on many branches.

A call tree. ways(4) calls ways(3) and ways(2). ways(3) calls ways(1) and ways(2). ways(2) appears twice, highlighted, once under ways(4) and once under ways(3), joined by a dashed line marked same call, solved again, and each calls ways(1) and ways(0). The same case is solved on both branches.
ways(4) calls ways(3) and ways(2), and ways(3) calls ways(2) again, so the same case is solved twice. Storing each answer the first time removes the repeat.

The playground counts the calls each version makes. The second version checks a map before it recurses and stores each answer it computes.

TypeScriptRuns in your browser
let calls = 0;

function ways(n: number): number {
  calls++;
  if (n <= 1) return 1;
  return ways(n - 1) + ways(n - 2);
}

const known = new Map<number, number>();
function waysStored(n: number): number {
  calls++;
  if (n <= 1) return 1;
  const hit = known.get(n);
  if (hit !== undefined) return hit;
  const answer = waysStored(n - 1) + waysStored(n - 2);
  known.set(n, answer);
  return answer;
}

for (const n of [10, 20, 30]) {
  calls = 0;
  const answer = ways(n);
  const plainCalls = calls;
  calls = 0;
  known.clear();
  const same = waysStored(n) === answer;
  console.log(`n=${n}: ${plainCalls} calls plain, ${calls} calls stored, same answer: ${same}`);
}

Each step of 10 in n multiplies the plain version's calls by more than a hundred. The stored version makes 2n - 1 calls.

When you review a loop, multiply the cost of its body by the number of times it runs. A search, a scan or a recomputation over n items inside a loop over n items makes the whole function O(n²), however innocent each line looks alone.

Check your understanding

6 questions on this lesson. Pick an answer to see whether it holds and why.

  1. 1An agent was asked to make this tag intersection fast for lists of tens of thousands of tags, and changed the callback to (tag) => new Set(b).has(tag). How does the changed version scale?
    TypeScript
    function sharedTags(a: string[], b: string[]): string[] {
      return a.filter((tag) => b.includes(tag));
    }
    Show the answer

    Answer B. new Set(b) runs inside the callback, so it copies all of b once per tag in a: O(a times b), the same order as the original includes scan and slower in practice. Engines do not cache a fresh Set between calls, and building one is linear, not a sort. Building the set once outside filter is what makes the whole thing O(a + b).

  2. 2An agent flags rows whose amount is above the average. What is the time complexity for n rows?
    TypeScript
    const average = (xs: number[]) => xs.reduce((s, x) => s + x, 0) / xs.length;
    
    const flagged = rows.filter((row) => row.amount > average(rows.map((r) => r.amount)));
    Show the answer

    Answer C. For each of the n rows, the callback calls map and reduce over all n rows, so the work is about n times 2n. Built-in methods still walk the array. The average never changes between rows, so computing it once above the filter makes the whole thing O(n). The methods run one after another inside each call, so they add instead of multiplying.

  3. 3A rate limiter keeps the timestamps of a client's recent requests. On each request it drops timestamps older than 60 seconds, appends the new one, and compares the count to the limit. Timestamps arrive in increasing order. Which structure fits?
    Show the answer

    Answer A. Because timestamps arrive in order, the oldest is always at the front and the newest goes at the back. A queue does both in O(1). A heap or sorted tree also finds the oldest, but pays O(log n) per operation to keep an order the arrival already gives you. A hash map has no notion of oldest at all.

  4. 4You time a function an agent wrote. At 10,000 items it takes 48 ms. At 100,000 items it takes 4,900 ms. What growth rate does that suggest?
    Show the answer

    Answer B. Ten times the input took about 100 times as long, which is what O(n²) predicts. Linear would be about 10 times, and n log n about 12 times. An exponential function would not finish at 100,000 items at all; a big jump in time is not by itself a sign of exponential growth.

  5. 5An agent replaced users.find((u) => u.email === email) inside a loop with a lookup in the map below. The tests pass. For which input do the two versions return different users?
    TypeScript
    const byEmail = new Map(users.map((u) => [u.email, u]));
    // later, inside the loop:
    const user = byEmail.get(email);
    Show the answer

    Answer B. Building a Map from pairs keeps the last value for a repeated key, while find returns the first match. With a duplicate email the map version returns a different user. A missing email gives undefined from both, and case matters equally to both. Keeping the first entry when building the map restores the old behavior.

  6. 6An agent wrote this to count paths across a grid. It is quick for small grids, and paths(20, 20) runs for minutes. What is the cause, and the fix?
    TypeScript
    function paths(r: number, c: number): number {
      if (r === 0 || c === 0) return 1;
      return paths(r - 1, c) + paths(r, c - 1);
    }
    Show the answer

    Answer A. paths(r - 1, c) and paths(r, c - 1) both go on to call paths(r - 1, c - 1), and the overlap compounds, so the call count grows exponentially. Storing each answer the first time cuts the calls to a number proportional to r times c. Turning the recursion into a loop that makes the same calls changes nothing about how many there are.

You understand it when you can

Drill

An agent wrote a function that removes duplicate email addresses by checking whether each one is already in the result list before appending it, and it passed tests with 50 addresses. Find its complexity, estimate its run time on 500,000 addresses, and rewrite it to run in linear time.

Topics

Big-O and Growth Rates
Describing how time and memory grow with input size, and which growth rates are acceptable at which sizes.
Core Data Structures
Arrays, hash maps, sets, trees, heaps and queues, and the operations each one makes cheap or expensive.
Searching and Sorting
Binary search and the common sorting algorithms, and when the built-in versions are the right answer.
Graph Algorithms
Breadth-first and depth-first search, shortest paths and topological sort applied to real routing and dependency problems.
Recursion and Dynamic Programming
Recognizing when a problem repeats subproblems, so you can tell an exponential agent solution from a linear one without writing the table by hand.
Constant Factors and Practical Cost
Why memory layout, constant factors and real input sizes sometimes matter more than the Big-O class.

Further reading

Start here

Short reads

Watch

  • 1. Algorithms and Computation. Jason Ku (MIT 6.006), 2020. 46-minute lecture.

    Opens MIT's 2020 algorithms course by defining correctness, efficiency and asymptotic notation with a concrete model of computation, the basis for stating any function's complexity.

  • CppCon 2014: Mike Acton "Data-Oriented Design and C++". Mike Acton, 2014. 88-minute talk.

    Shows with cache-miss arithmetic why memory layout and real data shapes can outweigh the Big-O class, which is the Constant Factors and Practical Cost topic.

Books

  • Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People. Aditya Y. Bhargava, 2024, 2nd edition.

    An illustrated tour of Big-O, hash tables, binary search, BFS, Dijkstra and dynamic programming; the 2nd edition adds trees and material on how modern CPUs affect data-structure performance.

  • The Algorithm Design Manual. Steven S. Skiena, 2020, 3rd edition.

    Its catalog and war stories teach you to match a described problem to the right data structure or algorithm, which is the competency this subsection asks for.

  • Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson and 2 others, 2022, 4th edition.

    The reference for rigorous analysis of sorting, hashing, graph algorithms and dynamic programming when you need to confirm a complexity claim.

Primary sources