S015 · Big-O Notation — Reasoning About Scale

Module M02: Math Foundations · Session 15 of 130 · Track: Math 📈

What you'll be able to do after this session

• Explain Big-O Notation — Reasoning About Scale to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S008 — Data Structures — list, tuple, dict, set (when to use what)

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Big-O Notation in 100 Seconds — Fireship — the fastest possible intro.
• 🎥 Deep dive (30–60 min) · Big-O Notation — CS Dojo — patient walkthrough with 6 example algorithms.
• 🎥 Hands-on demo (10–20 min) · NeetCode — Big O Notation Explained with Examples — LeetCode-style breakdown.
• 📖 Canonical article · Wikipedia — Big O Notation — the formal definition; skim the "Orders of common functions" table.
• 📖 Book chapter / tutorial · CLRS Chapter 3 — Growth of Functions (MIT OCW notes) — the textbook every CS grad reads.
• 📖 Engineering blog · High Scalability — Latency Numbers Every Programmer Should Know — turn Big-O into wall-clock intuition.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: How to talk about performance without measuring.

Imagine three delivery services. Service A adds one hour to every delivery no matter how many packages — 1 or 1000, same hour. Service B adds one minute per package. Service C's time grows with the square of the number of packages. For 10 packages, C is fastest. For 10,000, C is a disaster and A wins by miles. Big-O is exactly this — a way of describing how the cost of an algorithm grows as the input grows, ignoring one-time setup costs and constant multipliers.

We write O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ). Each is a shape, not a wall-clock time. O(1) is a hash-map lookup. O(log n) is binary search on a sorted list. O(n) is a single loop. O(n log n) is a good sort (merge, timsort). O(n²) is a nested loop over the same list. O(2ⁿ) is a naive recursive Fibonacci — hits a wall around n=40.

The forever-gotcha: Big-O hides constants that matter in real life. O(n) with a slow constant (network call per element) can be worse than O(n²) with tight in-memory operations on small n. Use Big-O to rule out bad algorithms; use a profiler to pick between good ones.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Growth rates side-by-side — plug in n = 10, 100, 10 000, 1 000 000 and see the collapse:

At ~10⁹ operations = ~1 second on a laptop. So O(n²) at n=10⁴ is ≈ 0.1 s (fine). At n=10⁶ it's ~10⁰⁰⁰ s ≈ 30+ hours. That's the cliff.

Worked example 1 — find a duplicate:

def has_dup_slow(xs):          # O(n²) — nested loop
    for i in range(len(xs)):
        for j in range(i+1, len(xs)):
            if xs[i] == xs[j]:
                return True
    return False
 
def has_dup_fast(xs):          # O(n) — one pass + O(1) set lookups
    seen = set()
    for x in xs:
        if x in seen:
            return True
        seen.add(x)
    return False

For n = 100 000 the slow version does 5 × 10⁹ comparisons (~5 s). The fast version does 100 000 (~1 ms). Same output, 5000× speedup — this is the shape of every Big-O win you'll ever have.

Worked example 2 — spot the hidden complexity:

def build(xs):
    result = ""
    for x in xs:          # loops n times, looks O(n)
        result += str(x)  # BUT string concat in Python is O(len(result)) → total O(n²)
    return result

The += on strings is not free — it copies. Use "".join(str(x) for x in xs) — that's O(n).

Space complexity works the same way but for memory. merge_sort is O(n) time-and-space; quick_sort is O(n log n) time but O(log n) space — matters when memory is tight.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

"""Empirically prove Big-O by timing algorithms across input sizes."""
import random, time
from typing import Callable
 
def has_dup_slow(xs: list[int]) -> bool:
    for i in range(len(xs)):
        for j in range(i+1, len(xs)):
            if xs[i] == xs[j]:
                return True
    return False
 
def has_dup_fast(xs: list[int]) -> bool:
    seen: set[int] = set()
    for x in xs:
        if x in seen:
            return True
        seen.add(x)
    return False
 
def bench(fn: Callable, n: int, trials: int = 3) -> float:
    best = float("inf")
    for _ in range(trials):
        xs = random.sample(range(n*10), n)   # unique, forces worst case
        t0 = time.perf_counter()
        fn(xs)
        best = min(best, time.perf_counter() - t0)
    return best
 
if __name__ == "__main__":
    sizes = [1_000, 2_000, 4_000, 8_000, 16_000]
    print(f"{'n':>8} | {'slow O(n²)':>12} | {'fast O(n)':>12} | speedup")
    print("-"*55)
    for n in sizes:
        s = bench(has_dup_slow, n)
        f = bench(has_dup_fast, n)
        print(f"{n:>8} | {s*1000:>10.1f}ms | {f*1000:>10.2f}ms | {s/f:>6.0f}x")

Observe when you run:

1. Each time n doubles, slow roughly quadruples (that's the O(n²) signature).
2. Each time n doubles, fast roughly doubles (that's O(n)).
3. The speedup column climbs from ~100× at n=1000 to ~1000×+ at n=16000.
4. If you push n=100_000 the slow version will take minutes — Ctrl-C it, that's your visceral proof.
5. Notice how identical the two outputs are (both return False) — Big-O is about speed, not correctness.

Try this modification: add a third algorithm has_dup_sort that sorts (O(n log n)) then scans adjacent pairs. Plot all three. You'll see has_dup_sort sits between the two — clearly better than n² but worse than the hash-set n.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Real Big-O wins happen when someone spots an accidental O(n²) inside a loop. Classic incident: Shopify's cart page once had a nested loop over line items that was O(n²) — fine at 10 items, unusable at 500 (an enterprise merchant). Fix: swap the inner lookup to a dict, O(n). Same trick, five hundred times a year, across the industry.

At Microsoft on the ODSP pipelines, I've caught O(n²) bugs by watching Spark job time grow faster-than-linear with data size. If doubling input quadruples time, you have a nested shuffle or a cross join. The fix is usually a broadcast join (small side broadcast, O(n) instead of O(n·m)) or a bucketed partition.

Common performance sins:

• in list inside a loop — that's O(n) per check → O(n²) total. Use set or dict for O(1) lookups.
• String concatenation in a loop — Python strings are immutable; each += copies. Use "".join(...).
• Deep nested pandas/Numpy loops — vectorise. A 100-line for-loop becomes a 3-line numpy call, 100× faster (this is really O(n) vs O(n) but with a 100× constant — matters!).
• N+1 queries in Django/SQLAlchemy — a loop that hits the DB per iteration → O(n) network round trips. Fix with select_related / prefetch_related → 1 query.

The Latency Numbers Every Programmer Should Know cheat-sheet is the other half of Big-O intuition: L1 cache 0.5 ns, RAM 100 ns, SSD 100 μs, network round-trip 500 μs, disk seek 10 ms. An O(n) algorithm that touches disk each step is worse than an O(n²) that stays in RAM, up to n ≈ 100 000. This is why databases fight so hard to keep hot data in memory.

At scale, teams also care about amortised complexity — Python's list.append is O(1) amortised (it doubles capacity), not O(n) even though occasionally it copies. And worst case vs average case — quicksort is O(n log n) average but O(n²) worst-case; timsort dodges this by being O(n log n) worst-case, which is why Python and Java both switched to it.

(e) Quiz + exercise · 10 min

1. Order these from fastest to slowest asymptotically: O(n²), O(1), O(n log n), O(log n), O(n), O(2ⁿ).
2. What's the complexity of "check if item is in a Python list" vs "check if item is in a Python set"? Why?
3. Why does += on strings inside a loop become O(n²)?
4. What's the difference between worst-case, average-case, and amortised complexity? Give an example of each.
5. An algorithm is O(n) but each step makes a network call (100 ms). A second algorithm is O(n²) but each step is an in-memory comparison (10 ns). At what n do they cross?

Stretch (connects to S008 Data Structures): given a list of 1 million integers, describe an O(n) algorithm to find the two numbers that sum to a target using a dict. Prove it's O(n) time and O(n) space. Now describe the O(n²) brute force and explain why the hash-map trick is the archetype of "trade memory for time".

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Big-O Notation — Reasoning About Scale? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S016): Discrete Math — Sets, Logic, Combinatorics, Graphs
• Previous (S014): Type Hints, mypy, dataclasses & pydantic
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.