Building Software
Sections

Contents

Section 4 of 9

Math and Algorithms

4 subsections, the core path through it Core 10.

Why it matters when agents do the typing

Every claim about correctness, speed or cost needs a check that does not depend on trusting its source, and math is the check you carry with you. Logic lets you reason about conditions and proofs, complexity tells you how code will scale before real data arrives, and statistics tells you whether a benchmark, a metric or an eval score means anything. Language models are probabilistic by construction, so reasoning about chance is part of everyday engineering.

The course: 4 lessons, about 34 minutes of reading, in the order below.

  1. 4.1

    Logic and Discrete Math

    Depth: explain

    Boolean logic, proof, sets, relations and graphs: the structures underneath conditions, databases, permissions and dependency systems.

    A mistake it teaches you to catch: An inverted or incomplete condition, such as a less-than where less-than-or-equal was needed, or a compound check negated incorrectly.

    Lesson: Reading Code as Logic 9 min

  2. 4.2

    Algorithms, Data Structures and Complexity

    Core 10 · Depth: do

    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.

    A mistake it teaches you to catch: A nested loop over two lists, taking quadratic time, where a hash map lookup would make it linear.

    Lesson: Reading Run Time Off the Page 8 min

  3. 4.3

    Probability and Statistics

    Depth: explain

    Distributions, sampling, variance and significance: the tools for judging whether a measurement, an experiment or an eval result means anything.

    A mistake it teaches you to catch: Average latency reported while a slow tail, which most users hit at least once per session, stays hidden.

    Lesson: Measuring Things That Vary 9 min

  4. 4.4

    Back-of-the-Envelope Estimation

    Depth: do

    Quick order-of-magnitude math for storage, throughput, latency, cost and time, done before building so bad designs fail on paper.

    A mistake it teaches you to catch: A design that needs tens of thousands of writes per second from a single database node sized for a few thousand.

    Lesson: Doing the Arithmetic Before the Build 8 min

Section test: Math and Algorithms

10 questions across the 4 lessons above. Take it after the course; each answer explains itself.

  1. 1An agent wrote this filter for the people a user can mention: anyone not banned and not deleted. bannedIds holds 50,000 IDs and users holds 200,000 people. Which rewrite returns the same people in linear time?
    TypeScript
    const mentionable = users.filter(
      (u) => !(bannedIds.includes(u.id) || u.deletedAt !== null),
    );
    Show the answer

    Answer C. Moving the ! inside the parentheses negates each part and turns || into &&, so a person must be missing from the banned set and not deleted. The Set makes each lookup constant time. The first option keeps ||, which lets a banned person through as long as they are not deleted. The includes version gives the right answer but scans up to 50,000 IDs for each of 200,000 people, up to 10 billion comparisons.

  2. 2A product page sends 20 calls in parallel, one to each of 20 shards on separate machines, and renders when the last one returns. Each shard answers in 30 ms at the median and 250 ms at its p99, and slow calls on different shards are unrelated. The page has a 200 ms budget. About what share of page loads include at least one call slower than 250 ms?
    Show the answer

    Answer B. Each call stays at or under its p99 with probability 0.99, so all 20 do with probability 0.99^20, about 0.82. The other 18% of page loads wait on at least one slow call, which puts roughly one load in five over budget. The p99 describes a single call. A page that waits for 20 of them is as slow as its slowest call, so it meets the tail far more often than 1 time in 100.

  3. 3The agent wants its eval to detect a 2-point gain near 80%, using the rule that a difference must reach two standard errors. Its plan reuses the case count from an older plan built for a 4-point gap. How many cases per version does a 2-point gap need, and roughly what does one comparison of the two versions cost?
    TypeScript
    // Plan for comparing prompt v1 and v2, which both score about 80%.
    const casesPerVersion = 800; // copied from last quarter's plan for a 4-point gap
    const smallestGap = 0.02;    // this time we want to see a 2-point difference
    const dollarsPerCase = (3_000 * 3 + 500 * 15) / 1e6; // input and output tokens
    console.log(casesPerVersion * 2 * dollarsPerCase); // 26.4
    Show the answer

    Answer B. The standard error of the difference is √(2 × 0.8 × 0.2 / n), and for a 2-point gap to reach two standard errors it must be at most 0.01, which gives n = 3,200. Because n sits under a square root, halving the gap you want to see quadruples the cases. At $0.0165 a case, 6,400 cases cost about $106. The 1,600 answer assumes cases grow in proportion to the precision, which leaves the eval unable to tell a real 2-point gain from noise.

  4. 4The leaderboard endpoint takes 2,000 requests per second. The agent says the sort is cheap because it is O(n log n). What does the arithmetic say?
    TypeScript
    const players: { name: string; points: number }[] = loadPlayers(); // 200,000, updated a few times a minute
    
    app.get("/leaderboard", (req, res) => {
      const top10 = [...players].sort((a, b) => b.points - a.points).slice(0, 10);
      res.json(top10);
    });
    Show the answer

    Answer A. A comparison sort makes about n log₂ n comparisons, and for 200,000 players a measured run made about 3.3 million, so 2,000 requests a second ask for over 6 billion. Measured under Bun on a laptop, one such sort took tens of milliseconds, so this endpoint needs dozens of CPU cores. O(n log n) is close to linear, but the whole cost is paid again on every request for a result that changes a few times a minute. Sort when the scores change and hand every request the saved top 10. Doubling the traffic doubles the work.

  5. 5An agent says this test proves the pricing function correct for every combination of flags. Roughly how long does one run take?
    TypeScript
    // The agent's "exhaustive" test for the pricing function.
    const flags = Object.keys(defaultFlags); // 30 boolean feature flags
    for (let mask = 0; mask < 2 ** flags.length; mask++) {
      const on = Object.fromEntries(flags.map((f, i) => [f, (mask & (1 << i)) !== 0]));
      expectPriceInvariants(price(cart, on)); // about 1 ms per case
    }
    Show the answer

    Answer C. Thirty independent booleans give 2^30 combinations, about 1.07 billion, and at 1 ms each that is about 1.07 million seconds, or 12 days. Each added flag doubles it. The 18-minute figure is 2^20 ms, the count for 20 flags. Past a couple of dozen inputs, enumeration stops being possible, and you test the boundaries, reason about how the conditions are built, or generate cases at random.

  6. 6The rule is that every admin can see every document in a shared folder. An agent's test picks 20 of the folder's 10,000 documents at random, opens each as one admin, and all 20 pass. Suppose 1% of the documents are in fact hidden from admins. How likely is it that all 20 still pass?
    Show the answer

    Answer D. Each random pick misses the hidden 1% with probability 0.99, so all 20 miss it with probability 0.99^20, about 82%. 18% is the chance the test catches the problem. A passing sample shows that some documents are visible to one admin, while the rule claims every document for every admin. Covering that takes many more generated cases across admins and documents, or an argument from how visibility is computed.

  7. 7An agent gives each share link a random 8-character hex ID and argues with this script that clashes can be ignored. The service will have 100,000 links by the end of the year. Roughly how likely is it that at least two of them share an ID?
    TypeScript
    const possibleIds = 16 ** 8; // 4,294,967,296
    const links = 100_000;
    console.log(links / possibleIds); // about 0.0000233, so 0.002%
    Show the answer

    Answer B. Every pair of links is a chance to clash, and 100,000 links make n(n − 1)/2, about 5 billion pairs, more than the 4.3 billion possible IDs. That gives about 1.16 clashing pairs on average, and the chance of at least one is 1 − e^−1.16, about 69%; a simulation agrees. The script's 0.002% is the chance that one new link hits an ID already taken. Adding those chances over all the links gives the expected number of clashes, 1.16, and an expected count can pass 1 while the chance of a clash stays below 100%. Use 128-bit random IDs, or a unique constraint that retries on a clash.

  8. 8An agent replaced a linear scan with this binary search. What does firstAtOrAfter([10, 20, 30], 99) return?
    TypeScript
    // Index of the first timestamp at or after t, or ts.length if there is none.
    // ts is sorted ascending.
    function firstAtOrAfter(ts: number[], t: number): number {
      let lo = 0;
      let hi = ts.length - 1;
      while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (ts[mid] < t) lo = mid + 1;
        else hi = mid;
      }
      return lo;
    }
    Show the answer

    Answer D. The loop keeps the answer between lo and hi, and the answer can be ts.length, but hi starts at ts.length - 1, so that answer is outside the range from the first step. The search narrows to index 2 and returns it, pointing at 30, which is before 99. Starting with hi = ts.length keeps the invariant and returns 3. The loop does finish: mid is always below hi, so each pass either raises lo or lowers hi.

  9. 9An agent rewrote a sort-and-merge step and reports it 25% faster: one run of the old version on 1,000 items took 2.8 ms, and one run of the new version took 2.1 ms. What should you ask for before you believe it?
    Show the answer

    Answer A. At about 2 ms, the timer, JIT warm-up and memory allocation are a large share of what gets measured, and one run per version says nothing about how much each varies with nothing changed. Time both at larger sizes, repeat each several times, and trust the gap only when it is well outside the spread of either. Big-O describes growth; two versions in the same class can differ in either direction at a given size.

  10. 10The agent tested this on 30 tickets. Production has 10,000. Counting input tokens only, roughly what does one run cost?
    TypeScript
    // Find support tickets that describe the same issue.
    for (let i = 0; i < tickets.length; i++) {
      for (let j = i + 1; j < tickets.length; j++) {
        // one model call: about 800 input tokens, at $3 per million input tokens
        if (await sameIssue(tickets[i], tickets[j])) link(tickets[i], tickets[j]);
      }
    }
    Show the answer

    Answer C. The inner loop starts at i + 1, so each pair is compared once: 10,000 × 9,999 / 2 ≈ 50 million model calls. At 800 tokens each that is 40 billion input tokens, about $120,000. $24 is one call per ticket, and $240,000 counts every ordered pair. The 30-ticket test made 435 calls for about a dollar, which is how a quadratic design passes a small test.