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. You'll derive the cost instead of memorizing it, read a problem's signature and match it to the right tool, and then run one relentless loop on anything too slow. And 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. That's 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: 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 actually 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. That's 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. A derived fact re-derives itself on demand, decades from now, in languages that don't exist yet. 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.

Here's why the ratio trick works before you ever run it. Suppose the cost really is proportional to n², and you feed the code n = 1,000. You'd expect about 1,000 × 1,000 = 1,000,000 units of work. Now double the input to n = 2,000, and the square becomes 2,000 × 2,000 = 4,000,000. The work went up by exactly 4×, because (2n)² = 4n², and that 4 is 2 raised to the hidden exponent. That's the whole trick: doubling the input makes the exponent print itself as a ratio you can read. If the cost were n³ the ratio would be 8, since 2³ = 8, and if it were plain n the ratio would be 2. Prediction first, measurement second — that's the habit. The probe below counts real operations at four doubling sizes, and you already know what number to look for.

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 actually 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.

What does a signature actually look like when you meet one in the wild? It's a phrase hiding inside the problem statement, and once you know the phrases they practically glow. "The data is already sorted", or "the answer flips once from yes to no", is the smell of binary search. "Have I seen this value before?", or "count how many times each item appears", is the smell of hashing (ch37). "The same subproblem keeps coming back" points at dynamic programming (ch40), and "the best local choice looks safe" points at greedy (ch39). Notice what you're doing here: you're not remembering algorithms, you're matching phrases to tools. That's why experts read a problem twice before they write a single line. The first read is for understanding, and the second is a deliberate signature scan. A signature can still mislead you, which is exactly why the loop in the next section re-checks the cost after every swap. The tree below is that scan, drawn out so you can practice it.

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 you first met in the brute-force chapter, promoted now to your default operating procedure. One: solve it the dumbest way that works, with brute force and no cleverness, just a correct answer. Two: measure the baseline by counting its operations and naming 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. The question sounds too simple to be the secret, but it is the secret. Every technique in the tree is just a named way of deleting one species of waste. Four: kill that waste with a technique from the tree, then re-check the complexity to confirm the curve actually dropped. Then loop.

Beat one deserves a defense, because every beginner resists it. Writing the dumb version feels like wasted effort when a cleverer answer clearly exists somewhere. But the brute-force version buys you two things nothing else can. First, it's a working oracle: when you later build the fast version, you can run both on a hundred random inputs, and any disagreement means the clever one is wrong. Second, it's a baseline: "7× faster" means nothing until there's a number to be 7× faster than. The professionals you admire write throwaway brute force constantly, and they feel no shame about it at all. The shame would be shipping a clever solution you never checked against a truth you could have had for ten lines of code. Start dumb on purpose, and say so without apology. Then let the next three beats earn the cleverness.

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 is brute force: check every pair with two nested loops, which the doubling probe from earlier would report as ratio 4, so it's O(n²). Beat three asks the question: what work actually repeats? For each number x you re-scan the whole list looking for target − x, asking "is this value present?" over and over again. Beat four: that exact phrase — "have I seen the value I need?" — is a trigger in the tree, and it points straight at hashing (ch37). Store each number in a set as you pass it, and the lookup becomes O(1), so the whole thing collapses to O(n). The set costs some memory, of course, and that's the trade at the heart of hashing: spend space to delete time. One pass through the loop turned a quadratic into a linear, and you never needed to be clever, only systematic. (Step it live in trace T30.)

One honest caveat before the next section: sometimes you scan for a trigger and nothing fires. That's not failure, that's information, and the loop tells you what to do with it. A powerful default when no signature glows is to sort the data first. Sorted order manufactures structure: it makes "is it present?" answerable by halving and puts equal items next to each other. Sorting costs O(n log n), which is cheap enough that it often pays for itself immediately. And if even that unlocks nothing, remember that the brute-force answer from beat one still works. Correct-but-slow ships, teaches you the problem's shape, and hands you the baseline for the day a bigger input forces the next lap. Real production incidents are mostly this case, by the way — no neat trigger, just the loop run honestly. The loop never leaves you empty-handed, and that is the entire point of having a procedure instead of a talent.

Put real numbers on the two-sum collapse, because the size of the win is easy to underestimate. With a list of 10,000 numbers, checking every pair costs on the order of 10,000 × 10,000 = 100,000,000 comparisons. The hashed version does one set lookup per number, which is about 10,000 cheap steps in total. Divide the two counts and the improvement is 100,000,000 / 10,000 = 10,000×, from one structural change and zero tuning. At a million numbers the brute force needs a trillion comparisons, which is simply not a plan. It also matters why the set lookup is cheap. A set hashes each value to a bucket address and jumps straight there, as ch37 showed, so membership costs about the same at ten items or ten million. The speedup isn't a percentage, it's a change of category, and the gap widens as the input grows.

you type
$ python triggers.py

import heapq, bisect, itertools
from collections import Counter, deque
from functools import cache

data = [7, 3, 9, 1, 9, 4, 7, 7, 2]

# sorted, and "where does it go / is it here?"   -> bisect
s = sorted(data)
print(s, bisect.bisect_left(s, 7), bisect.bisect_right(s, 7))

# "have I seen it?" / "how many times?"          -> set / Counter
print(len(set(data)), Counter(data).most_common(2))

# "the best k" (NOT the whole order)             -> heapq
print(heapq.nlargest(3, data), heapq.nsmallest(2, data), max(data))

# "fewest hops through a network"                -> BFS + deque
g = {"a": "bc", "b": "d", "c": "d", "d": ""}
def hops(g, src):
    dist, q = {src: 0}, deque([src])
    while q:
        u = q.popleft()
        for v in g[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist
print(hops(g, "a"))

# "the same subproblem keeps coming back"        -> functools.cache
@cache
def fib(n): return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib(90), fib.cache_info().currsize)

# "every pair / every combination"               -> itertools
print(len(list(itertools.combinations(range(9), 2))), 9 * 8 // 2)

# "the smallest X that still works"              -> binary-search the ANSWER
def first_true(lo, hi, ok):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if ok(mid): hi = mid
        else:       lo = mid + 1
    return lo
print(first_true(1, 10**9, lambda k: k * k >= 10**12))

# no trigger fires?                              -> sort first, then look again
runs = [(k, len(list(v))) for k, v in itertools.groupby(sorted(data))]
print(runs)

you see
[1, 2, 3, 4, 7, 7, 7, 9, 9] 4 7
6 [(7, 3), (9, 2)]
[9, 9, 7] [1, 2] 9
{'a': 0, 'b': 1, 'c': 1, 'd': 2}
2880067194370816120 91
36 36
1000000
[(1, 1), (2, 1), (3, 1), (4, 1), (7, 3), (9, 2)]

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, and once you've picked the right curve, that discarded constant is the entire remaining game. Pin down what that constant literally is. If an algorithm does c machine steps per item, its true cost is roughly c × n, and Big-O drops the c because it never changes the curve's shape. But c is real seconds on a real machine. Two algorithms at the same O(n) can differ by 5× or 50×. The difference is how kindly they treat the machine from Volume 1: whether the data they walk is already in the CPU's fast cache, whether the branches they take are predictable, whether the work can 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, so both are flatly, provably O(n). Run the doubling probe on either one and you get ratio 2. Yet on this run the hand-written loop took about 113 ms and the built-in sum() about 16 ms — roughly 7× apart at the same complexity. (That's wall-clock on one machine, so 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. You wrote the same algorithm both times. You just paid the interpreter's toll five million times in one of them. Same curve, very different constant. The second pair shows the memory hierarchy doing the same thing, this time 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, so their cost is identical: O(R·C). But row_major walks memory the way it's laid out. It grabs one row, which is 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, defeating the cache. Nothing about the arithmetic changed, only the order of the memory addresses. Remember the bill from Volume 1: a cache hit costs a few processor cycles, while a trip out to main RAM costs hundreds. Paying that toll costs about 1.5× more here (131 ms vs 200 ms) for the very same additions. In pure Python the interpreter dilutes the effect, but 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.

These two experiments hand you a rule: fix the curve first, then fight the constant. Here's why the order can't flip: take the quadratic two-sum at n = 10,000, which costs about 100,000,000 comparisons. A heroic 7× constant-factor win, like the sum() gap, still leaves roughly 14 million steps, because 100,000,000 / 7 ≈ 14,000,000. The hashed O(n) version does about 10,000 steps, with no heroics anywhere. No amount of machine sympathy rescues the wrong curve. This is also why premature micro-optimization has such a bad name: it polishes the constant on a curve that should have been replaced. But once the curve is right, the constant is the only lever left, and that's when you reach for built-ins, cache-friendly walks, and the C underneath your libraries. The curve picks the winner at scale, and the constant picks the winner among correct curves.

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: in your git history, your commute, your errands. Once the reflexes are in, you start applying them without noticing, which is the real "you use this every day" moment. Watch the volume's ideas escape the terminal.

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, and 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, and we computed the result: 20 checks, not a million. The 20 is easy to verify, because 2¹⁰ = 1,024 covers a thousand commits and 2²⁰ = 1,048,576 covers the full million. Ten more doublings buy a thousand times more history for ten more checks. That is the absurd generosity of the logarithm, and it never stops paying. 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, straight from the randomization chapter: don't react to the scary outcome, weight it by its probability. And the rest fold in the same way: greedy your errands by visiting the nearest stop next (ch39). Hash your memory by writing things 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, just cache the answer and reuse it (ch40).

If expected value still feels abstract, run the commute ten times in your head. The train normally takes 25 minutes, and the delay strikes on roughly one trip in ten. So nine mornings cost 25 minutes each, which is 9 × 25 = 225, and the unlucky tenth costs 25 + 40 = 65. Add them up and the ten commutes total 225 + 65 = 290 minutes. Divide by the ten trips and the average is 29 minutes, exactly what the formula promised. That's all expected value is: the long-run average, computed before you have to live it. The one scary morning is real, but it's one morning in ten, even though your gut weights it like five. Quants make a living on exactly that gap between felt risk and computed risk.

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 honestly it's smaller than it looked from the outside when we started. Count the work, watch the growth, and match the problem's signature to the right tool in the tree. Brute-force a correct answer first, find the wasted work, delete it, then re-check the curve, and respect the constant once the curve is right. Then run that loop on everything you touch, code and otherwise, until it stops being something you do and becomes something you are. The loop is small enough to hold in one hand and sharp enough to cut any problem you meet. That's the 1%. Not a different kind of mind. The same mind, running a better loop, relentlessly.

If you carry only one thing out of this volume, carry the two questions from the figure above. How does the work grow? and where is the waste? — that pair is the entire kernel, and everything else we built is machinery for answering them fast. Ask them this week on real code: the report that feels slow, the test suite that crawls, the script you're a little afraid of. The first few times will feel deliberate and clunky, the way counting beats feels to a new musician. That's fine, because deliberate is how reflexes start, and every rep makes the next one cheaper. We don't fully know how far this way of seeing can carry a person, and honestly that's the exciting part. Somewhere past the drills, the questions stop being questions and become how you look at everything. Go find out.

# ---------------------------------------------------------------
# 1. "count how many times each item appeared"  -> HASHING: Counter
#    WHY: the trigger is "per item, how many" — one pass, O(1) per
#    event, and .most_common(3) is the "worst three" for free.
#
# 2. "the fewest X that still works"            -> BINARY-SEARCH THE ANSWER
#    WHY: more robots is never worse, so "can k robots finish in 4h?"
#    is monotone — false, false, then true forever. Search k, not jobs.
#
# 3. "must happen before" + "shout if there's a loop" -> DFS TOPOLOGICAL SORT
#    WHY: "A before B" IS a directed edge; recording each node when it
#    FINISHES lists prerequisites first, and a back-edge is the cycle.
#
# 4. "the best ten out of two million"          -> HEAP: heapq.nlargest
#    WHY: you want a RANK, not an order. O(n log k) with k = 10; sorting
#    two million quotes to read ten of them is the wrong question.
#
# 5. "the same or not, without comparing the contents" -> HASHING: fingerprint
#    WHY: turn each object into one number and compare numbers. A match
#    is a CANDIDATE — confirm it with a real compare, because collisions
#    are possible and a wrong "duplicate" deletes someone's photo.
#
# THE META-ANSWER: 1 and 5 are both hashing. One arrived dressed as
# counting, the other as comparison — and that is the entire lesson of
# this chapter. You are not matching problems to algorithms. You are
# stripping the costume off, and there were only ever a dozen faces
# underneath.
# ---------------------------------------------------------------

import heapq, hashlib
from collections import Counter, defaultdict

# 1 — tally: "how many times did each error code appear?"
log = ["E500", "E404", "E500", "E301", "E500", "E404"]
print(Counter(log).most_common())

# 2 — binary-search the answer: "fewest robots that still make the deadline"
picks = [7, 2, 5, 10, 8, 3, 9, 4]
def minutes(robots):
    loads = [0] * robots
    for p in sorted(picks, reverse=True):     # longest job to the freest robot
        i = loads.index(min(loads))
        loads[i] += p
    return max(loads)
def first_true(lo, hi, ok):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if ok(mid): hi = mid
        else:       lo = mid + 1
    return lo
print([(r, minutes(r)) for r in range(1, 6)],
      first_true(1, len(picks), lambda r: minutes(r) <= 15))

# 3 — topological sort: "what order do I build these, and is there a loop?"
def build_order(dep):
    colour, out = {}, []
    def visit(u):
        if colour.get(u) == 1: return False       # back-edge -> a cycle
        if colour.get(u) == 2: return True
        colour[u] = 1
        for v in dep.get(u, ()):
            if not visit(v): return False
        colour[u] = 2
        out.append(u)                             # record on FINISH
        return True
    return out if all(visit(u) for u in dep) else None
dep = {"app": ["ui", "core"], "ui": ["core"], "core": ["util"], "util": []}
print(build_order(dep))
dep["util"] = ["app"]
print(build_order(dep))

# 4 — top-k from a stream: never sort two million quotes
quotes = [("AAPL", 0.03), ("TSLA", 0.41), ("MSFT", 0.02),
          ("GME", 1.90), ("NVDA", 0.11), ("AMC", 0.77)]
print(heapq.nlargest(3, quotes, key=lambda q: q[1]))

# 5 — fingerprint, then confirm: dedupe without comparing pixels
files = {"a.png": b"sunset over the pier", "b.png": b"sunset over the pier",
         "c.png": b"the dog, blurry"}
buckets = defaultdict(list)
for name, blob in files.items():
    buckets[hashlib.sha256(blob).hexdigest()[:12]].append(name)
dupes = [names for names in buckets.values()
         if len(names) > 1 and files[names[0]] == files[names[1]]]
print({k: v for k, v in buckets.items()}, "->", dupes)


# ---------- the actual run, python 3.12.7 ----------
#
# [('E500', 3), ('E404', 2), ('E301', 1)]
# [(1, 48), (2, 24), (3, 17), (4, 12), (5, 10)] 4
# ['util', 'core', 'ui', 'app']
# None
# [('GME', 1.9), ('AMC', 0.77), ('TSLA', 0.41)]
# {'fc62bd8121d8': ['a.png', 'b.png'], '5ae0dff71eb3': ['c.png']} -> [['a.png', 'b.png']]
#
#
# ---------- reading it ----------
#
# 2. Look at the pairs: 3 robots finish in 17 minutes, 4 finish in 12.
#    The deadline of 15 sits between them, so 4 is the answer and the
#    search found it in log2(8) probes without ever trying every count.
#    Note the honesty: minutes() is a GREEDY estimate, not the true
#    optimum, so the answer is "fewest under this scheduling policy" --
#    name your feasibility check before you trust its verdict.
#
# 3. The valid order came out util, core, ui, app -- every dependency
#    to the left of the thing that needs it. Then one added edge
#    (util needs app) makes the graph cyclic and the function returns
#    None. That None is not a failure; it is your build tool saying
#    "these two packages need each other" -- the most useful error
#    message a dependency resolver ever prints.
#
# 5. Two files with identical bytes landed in the same bucket, and the
#    code still ran a real == before calling them duplicates. That extra
#    line is the difference between a fast filter and a data-loss bug.

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. →