47How to think like the 1%

In Chapter 46 we reached for randomness when an exact answer cost too much. That was the last technique in a volume full of them. This chapter teaches no new algorithm. It teaches the thing underneath all of them: the operating system for an algorithmic mind, the handful of reflexes that turn a whole volume of techniques into one way of seeing. Here's the plan. We take the moves you already own and watch them collapse into habits you run without thinking: derive the cost instead of memorizing it, read a problem's signature and match it to the right tool, then run one relentless loop on anything too slow. The whole way through, we keep asking the one thing that actually matters — sat in front of a problem you've never seen, what do you actually do first? The gap between code that melts under load and code that scales to a billion users isn't a bigger memory or a faster brain. It's that loop, run so many times it became instinct. By the end you'll know exactly what to ask, what to reach for, and how to tell whether your fix actually worked — the whole volume, folded into a way of thinking you can carry anywhere.

01Derive it — never memorize it

Let's start with the single worst way to learn this material: memorizing a table — sorting is n log n, hashing is O(1), and so on down the page. Watch what that does to you. Memorized facts rot. And they teach you nothing about the problem in front of you that isn't already sitting in that table. The 1% do the exact opposite. They derive the complexity on the spot, by counting the work as the input grows — the precise move you built back in the growth-zoo chapter. The growth zoo was never a list to recite; it's a lens you look through. And there's a shortcut that makes the derivation almost mechanical: count the operations at some size n, then again at 2n, and read the ratio.

def quad(n):                 # a full nested loop
    ops = 0
    for i in range(n):
        for j in range(n):
            ops += 1
    return ops

for n in (1000, 2000, 4000, 8000):
    print(n, quad(n))
# 1000 1000000   |  double n -> 4x the work
# 2000 4000000   |  ratio 4  ->  the exponent is 2
# 4000 16000000  |  ratio 4  ->  O(n squared)
# 8000 64000000  |  ratio 4

Read it line by line. quad just tallies how many times the inner body runs. We call it at four sizes, each double the last, and print the count. The counts we got were 1,000,000, then 4,000,000, then 16,000,000, then 64,000,000. Every time we doubled n, the work went up four-fold. That ratio is the answer. Doubling the input and getting 4× the work means cost ∝ n², because 4 = 2². You never had to remember that nested loops are quadratic — you watched the exponent fall out of the ratio. Run the same probe on six different shapes and the ratios sort themselves into the whole zoo:

So you can name any single function's growth on sight. But real work isn't "name this loop" — it's "I have a problem; which tool do I even reach for?" That needs a different reflex →

02The toolkit is a flowchart, not a menu

Beginners keep their algorithms in a list and scan it hopefully, top to bottom. Experts keep them in a decision tree keyed on the signature of the problem — a handful of tell-tale features that each point straight at a technique. Learn the triggers, not just the tools. Here is the whole volume compressed into that tree. Read the problem, spot the signature, follow the arrow.

The tree tells you what to reach for. But what do you do before you know the answer — when nothing in the tree obviously fits? You run the loop →

03The loop that cracks a problem you've never seen

Here is the method that survives contact with the unknown: the four-beat cycle from the brute-force chapter, now as your default operating procedure. One: solve it the dumbest way that works — brute force, no cleverness, just a correct answer. Two: measure the baseline — count its operations, name its Big-O. Three: ask the one question that unlocks everything — where is the wasted work? Look for the thing you compute again and again, the search you redo, the pair you re-examine. Four: kill that waste with a technique from the tree, then re-check the complexity to confirm the curve actually dropped. Then loop.

Watch it turn on a problem you've already met. Two-sum: find two numbers in a list that add to a target. Beat one, brute force: check every pair. That's two nested loops, and the doubling probe from earlier would report ratio 4, so it's O(n²). Beat three, the question: what work repeats? For each number x you re-scan the whole list looking for target − x. You keep asking "is this value present?" over and over. Beat four: that exact phrase — "have I seen the value I need?" — is a trigger in the tree, and it points at hashing (ch37). Store each number in a set as you pass it, and the lookup becomes O(1). The whole thing collapses to O(n). One pass through the loop turned a quadratic into a linear. You didn't need to be clever — you needed to be systematic. (Step it live in trace T30.)

The loop drops your Big-O. But two programs with the same Big-O can still finish minutes apart. To win there, you have to think about the metal →

04Respect the constant — machine sympathy

Big-O is necessary, not sufficient. It deliberately throws away the constant factor. Once you've picked the right curve, that discarded constant is the entire remaining game. Two algorithms at the same O(n) can differ by 5× or 50×, depending on how kindly they treat the machine from Volume 1. Is the data they walk already in the CPU's fast cache? Are the branches they take predictable? Can the work spread across cores? Here are two pairs, each with identical Big-O, timed on this machine:

data = list(range(5_000_000))

# both O(n): sum by hand vs. the built-in
def manual():
    t = 0
    for x in data: t += x
    return t

def sum_data(): return sum(data)
from timeit import Timer
def best(f): return min(Timer(f).repeat(repeat=5, number=1)) * 1e3   # ms, best of 5

print("manual loop:", round(best(manual), 1), "ms")   # ~113 ms (same Big-O)
print("builtin sum:", round(best(sum_data), 1), "ms")  # ~16 ms  (~7x faster)

Both loops touch all five million items exactly once — flatly, provably O(n), and the doubling probe gives ratio 2 for each. Yet on this run the hand-written loop took about 113 ms and the built-in sum() about 16 ms. That's roughly 7× apart at the same complexity (wall-clock on one machine; your numbers will differ, but the ordering won't). The gap is pure constant. The interpreter re-dispatches Python bytecode on every pass of the hand loop, while sum() runs the same additions in a tight C loop with far less overhead per element. Same curve, very different constant. The second pair shows the memory hierarchy directly:

grid = [[1]*2000 for _ in range(2000)]   # 4,000,000 cells

def row_major():           # walk each row fully before the next
    s = 0
    for r in range(2000):
        row = grid[r]
        for c in range(2000): s += row[c]
    return s
# row-major: 131 ms   |   col-major (swap the loops): 200 ms  -> ~1.5x, same O(R·C)

Both nested loops visit all four million cells — identical O(R·C). But row_major walks memory the way it's laid out. It grabs one row (a contiguous run of references) and marches straight along it, so the values it needs next are already sitting in cache. Swap the loops to go column-first, and every single step jumps to a different row-list. That defeats the cache and costs about 1.5× more here (131 ms vs 200 ms) for the very same additions. In pure Python the interpreter dilutes the effect; in the C or Rust underneath your libraries the same swap can cost 5–10×. The Big-O saw none of this — the machine saw all of it.

That's the engineering. But the deepest payoff of this whole volume is that the reflexes work off the computer entirely — on your errands, your bugs, your decisions →

05Run the loop on your life

The reason these ideas feel powerful is that they were never really about code. They're about structure, and structure is everywhere. Once the reflexes are in, you start applying them without noticing. That's the real "you use this every day" moment.

import math
# BINARY-SEARCH your debugging: a bug appeared somewhere in your commit history.
# "good before, broken after" is monotonic -> bisect it, don't read every commit.
for commits in (100, 1000, 100_000, 1_000_000):
    print(commits, "commits ->", math.ceil(math.log2(commits)), "checks")
# 100 -> 7   |   1000 -> 10   |   100000 -> 17   |   1000000 -> 20

That's git bisect, and it's the binary-search chapter wearing overalls. A million commits hide a bug. Reading them one by one is O(n) — a million checkouts. But "works before the bad commit, fails after" is monotonic, and monotonic is a trigger for binary search: test the middle, throw away half, repeat. We computed it: 20 checks, not a million. That's O(log n) applied to your own workflow, and it's why "bisect it" is the fastest debugging advice anyone will ever give you. The other techniques transfer just as cleanly:

# EXPECTED-VALUE your risks (quant thinking for life): train vs. drive.
p_delay, delay = 0.10, 40         # 10% chance the train loses 40 minutes
train = 25 + p_delay * delay      # base 25 min + expected delay
drive = 35                        # flat, "safe"
print(round(train,1), "vs", drive)   # 29.0 vs 35  -> take the "risky" train

The train feels risky because of that 40-minute tail. But expected value — probability × cost — puts the delay at just 0.10 × 40 = 4 minutes. So the train averages 29 minutes against the drive's 35. The "safe" choice was slower. That's the quant's core move (the randomization chapter): don't react to the scary outcome, weight it by its probability. The rest fold in the same way — greedy your errands (visit the nearest stop next, ch39), hash your memory (write it down so recall is O(1) instead of re-deriving it, ch37), and DP your decisions (never re-solve a problem you've already solved — cache the answer, ch40).

So how do you drill these until they're automatic — until you see in growth curves and triggers without trying? →

06The gap is a loop, run relentlessly

Here is the honest, slightly deflating, deeply encouraging truth this volume has been building toward: the distance between the 99% and the 1% is not talent. It is not a gift you were or weren't born with. It is this handful of reflexes, practiced until they became how you see — and reflexes are trainable. Five drills turn the ideas in this book into instinct:

• Derive the complexity of everything you read. Every function in every codebase, every snippet in every article — before you move on, count its work and name its Big-O. Make it a tic. This is how "what's the growth?" becomes automatic.
• Re-derive one classic a day, from scratch. Binary search, merge sort, the two-sum trick — rebuild one each morning without looking. You'll discover how much you'd only memorized, and each rebuild files it deeper as a method, not a fact.
• Explain it out loud. If you can't say why quicksort is n log n on average to an imaginary beginner, you don't own it yet. Teaching is the fastest debugger for your own understanding.
• Always solve, then optimize. Get a correct brute-force answer first — every single time — then run the loop. Cleverness before correctness is how you ship fast, wrong code.
• Ask the two questions, on everything. What is the input size? Where is the wasted work? Those two questions, asked reflexively, are the bulk of what separates the engineer from the coder.

That is the whole message of Volume 3, and it's smaller than it looked from the outside. Count the work. Watch the growth. Match the signature to the tool. Brute-force, find the waste, delete it, re-check. Respect the constant. Then run that loop on everything you touch — code and otherwise — until it stops being something you do and becomes something you are. That's the 1%. Not a different kind of mind. The same mind, running a better loop, relentlessly.

Where the series goes next. You now think about cost like an engineer. The next volume gives you the vocabulary of structure to act on it: the 13 must-know data structures — dynamic arrays, linked lists, stacks and queues, hash maps, binary search trees, heaps, tries, graphs, and the rest — each one a deliberate trade of space for time, and each the reason some operation in this volume was O(1) instead of O(n). You've learned to read the price. Next, you learn to build the machines that set it. →