Big-O Notation — Reasoning About Scale

Review boundary and corrected contracts

Big-O is an asymptotic upper bound, not necessarily a tight linear law. Benchmarks can falsify a performance expectation but cannot prove an asymptotic bound. Comparison sorting lower bounds concern arbitrary distinct inputs; adaptive best cases and bounded-key sorts are different assumptions.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Look at a snippet of code and, without running it, predict how its runtime and memory will scale — and know when an asymptotic model does not predict a particular timing.

Why this session exists

Two engineers write code that does the same thing. On 1000 rows, both finish instantly. On 10 million rows, one finishes in 3 seconds and the other times out after 20 minutes. In an illustrative case the difference can be linear versus quadratic work; real timings also depend on implementation, hardware and input distribution. Big-O is the vocabulary that lets you predict this before you write the code, and diagnose it before you profile. Skip this and you'll spend your career surprised by performance. Learn it and you'll pick the right data structure the first time.

You will be able to

• Read a loop and say its Big-O out loud (n, n log n, n², etc.) without hesitation.

• Explain why a tight n log n growth eventually beats tight n² growth for fixed positive constants, without promising a universal crossover size.

• Distinguish worst-case, average-case, and amortised cost — and give one example of each.

• Explain why a theoretically slower algorithm can win in practice (cache, constants, small n).

• Sketch the shape of every common curve — 1, log n, n, n log n, n², 2ⁿ — on a napkin.

Prerequisites

• S005–S008 — you can read Python loops, list comprehensions, and function calls.
• Basic algebra (exponents, logs). No calculus required.

Pre-read · skim before the session (25 min total)

Further reading: Big-O Cheat Sheet

Further reading: Big O notation

Further reading: The power of two random choices

Optional archived videos

These are retained original resource URLs, not independently verified titles, speakers, durations or technical evidence. Use the official readings above for API contracts.

• Original video 1 — optional background; availability and attribution unverified.
• Original video 2 — optional background; availability and attribution unverified.
• Original video 3 — optional background; availability and attribution unverified.

(a) Intuition · 5 min

Big-O is a delivery contract, not a delivery time

Real: Two moving companies quote you. Company A: "we charge per box." Company B: "we charge per box times per box." For 10 boxes, both are cheap. For 10 000 boxes, one quote is 10 000× the other. That multiplication of scale-shape is Big-O. Big-O is not "how long will this take?" It's "how does the cost grow as the input grows?" A 10-line function running on a laptop can take a millisecond or a millennium depending on the shape.

For nonnegative costs, $T(n) ∈ O(f(n))$ means there are constants $c>0$ and $n_0$ such that $T(n) ≤ c f(n)$ for every $n ≥ n_0$. It is an upper bound: a constant function is also O(n). A matching lower bound gives Θ(f(n)). Even Θ(n) alone need not give an exact doubling ratio; a model such as T(n)=an+b predicts roughly double work at sufficiently large n.

Loops supply counts, not a visual rule: an outer loop of n and an inner loop of m with constant work gives Θ(nm) when both execute fully. A nested loop that runs only a fixed three times adds a constant, while a loop that repeatedly halves a remaining interval takes O(log n) iterations. Count the work inside each iteration and early exits.

The shapes you actually see

The complexity ladder, from best to worst

• O(1) — bounded by a constant independent of n in the model. Array indexing; average hash-table lookup with bounded-cost hash/equality.

• O(log n) — logarithmic. Binary search, balanced tree operations. Halves the problem each step.

• O(n) — linear. Walk once through the input. sum(xs), max(xs), single-pass filter.

• O(n log n) — linearithmic. Efficient comparison sorts (merge, heap, quicksort avg).

• O(n²) — quadratic upper bound. A full pair scan has Θ(n²) comparisons; feasibility depends on operation cost and the budget.

• O(2ⁿ) — exponential. There are 2ⁿ subsets; copying each subset can add an n factor. No universal cutoff at n=25 exists.

• O(n!) — factorial. There are n! permutations; materialising/scoring each can add an n factor. Budget work rather than assuming a cutoff at n=12.

Big-O hides the constant — and that can matter

Big-O drops constants: 3n + 1000 is O(n). But at small n, the constant dominates. Insertion sort can beat more elaborate sorts on small inputs, but n=16 is not a universal crossover. CPython extends short natural runs using binary insertion sort; those implementation details and constants are measured separately from the asymptotic class. Theory and practice both matter; ignore either at your peril.

A quick history

The mathematical history and the engineering cost model are different subjects. Knuth lists Big Omicron and Big Omega and Big Theta in his author-hosted collected papers; the NIST definition makes the upper-bound convention explicit. The older timeline attached precise dates to Bachmann, textbook adoption and hardware trends without source passages establishing those events here. Those dates are not used as evidence for an algorithmic claim. Cache hierarchies, SIMD and GPUs motivate additional cost models, not a universal 100× speedup or a single decade when constants began to matter.

(b) Reading growth before measuring runtime · 15 min

How each shape grows (a table of model functions)

To separate growth from machine speed, hold the kind of operation fixed and increase the input size. Compare adjacent input sizes in the diagram, especially the linear and quadratic rows, before translating loop structure into a cost estimate.

A tenfold increase in input produces ten times the work in the linear row but one hundred times the work in the quadratic row. These are growth comparisons, not timings; the next steps connect them to loops, and the later experiment measures actual implementations.

How to read a loop in your head

Count loops that scan the input

Desc: One loop over n items → O(n). Two nested loops over the same n → O(n²). Loop over n inside a loop over m → O(n · m).

Look for halving/doubling

Desc: Computing a midpoint is not enough. If every iteration updates lo or hi to discard about half the interval and makes progress, the iteration count is O(log n). Without the update, that loop may never terminate.

Recurse and count the recursion tree

Desc: T(n) = 2·T(n/2) + O(n) → merge-sort → O(n log n). Master Theorem gives you the shortcut.

Drop constants and lower-order terms

Desc: 3n² + 100n + 42 → O(n²). Only the fastest-growing term survives.

Sanity check: is the answer plausible?

Desc: If you get O(1) for something that walks the list, you dropped a loop. If you get O(n^7), you probably counted a constant loop.

Common data-structure operations (memorise this)

Operations you'll do 10 000 times a year

Name: list[] index / append

Desc: List indexing is O(1) worst-case in the reference model. Append is O(1) amortised, with O(n) resizing events. Front insertion/deletion shifts O(n) references.

Name: dict / set lookup + insert

Desc: O(1) average under bounded-cost hash/equality and well-distributed hashes; collisions can produce O(n) lookups. Python randomises hashes for some built-in types such as str/bytes, not every custom key or integer.

Name: sorted list · binary search

Desc: O(log n) lookup, O(n) insert (shifting). Great for read-heavy workloads.

Name: heap (heapq) push/pop

Desc: Heap repair uses O(log n) comparisons for push/pop and peek-min is O(1); assume bounded-cost comparisons and account for amortised underlying list allocation separately. Useful for priority queues and top-k problems.

Name: balanced BST versus SortedList

Desc: A balanced search tree supports O(log n) lookup/insert/delete, but visiting all n values is Θ(n). sortedcontainers.SortedList is a segmented-list design, not a balanced BST; its detailed update cost depends on sublist size and splitting. Do not import a tree bound into a different representation.

Name: linked list append/prepend

Desc: Linked-list insertion at a known head/tail is O(1) when the needed pointer is maintained; finding an indexed position is O(n). Python collections.deque supports efficient end operations but is a block-based deque, not a plain node-per-element linked list.

Worst-case vs average vs amortised

Name: Worst-case

Tagline: The pessimist's promise

• Guaranteed upper bound on ANY input

• A step-count bound is useful but does not certify a hard real-time deadline without bounded platform/operation costs

• Quicksort can take Θ(n²) for repeatedly unbalanced partitions; sorted input triggers this for naive endpoint-pivot variants, not every implementation

• Guides pathological-input decisions

Name: Average-case

Tagline: The statistician's estimate

• Expected cost over random inputs

• Assumes an input distribution

• Quicksort average: O(n log n)

• Guides typical-workload decisions

Name: Amortised

Tagline: The banker's account

• Expensive operations paid for by many cheap ones

• list.append is O(1) amortised (resize is O(n) but rare)

• Union-Find with path compression plus union by rank/size has inverse-Ackermann amortised bounds over operations; path compression alone is not the stated theorem

• Guides throughput analysis

Mental model

Two questions before writing any performance-sensitive code

1. What is n going to be? If n is bounded to 1000, compute the actual operation count and cost before deciding an O(n²) method is acceptable. 2) What is the constant hiding behind the O? A cache-friendly O(n²) loop can beat a pointer-chasing O(n log n) tree at every n your app will ever see. Measure when it matters.

Myth: "O(n log n) beats O(n²), so the lower-complexity algorithm is the faster one. Big-O tells me which implementation to pick."

Truth: Big-O gives an asymptotic upper bound as n grows, not necessarily the tight growth rate. Even when tight rates are known, constants and lower-order terms affect finite inputs. Two algorithms in the same class can differ by orders of magnitude in wall-clock time, and a "worse" class routinely wins below some crossover point — which is why real sort implementations switch to insertion sort for small subarrays.

Why: Because for the large inputs used to teach it, the claim is true, and asymptotics genuinely is the right tool for choosing between a linear scan and a hash lookup at scale. What the notation hides is everything that dominates at realistic sizes: the constant factor, memory access patterns, and the fact that a sequential array scan and a pointer-chase through a linked structure have identical O(n) but wildly different real cost, because one may use predictable accesses while the other can suffer more cache misses; a miss on every element is not guaranteed. The gap between "same complexity" and "same speed" is where most performance work actually lives, and Big-O is structurally incapable of showing it to you.

Test: same asymptotic class, potentially different constants. The optional NumPy example below measures this machine and integer range only, not a universal ratio. Python ints are arbitrary precision; NumPy's fixed-width integer sums can overflow outside this bounded example.

import timeit
setup = 'import numpy as np; a = list(range(10_000)); b = np.arange(10_000, dtype=np.int64)'
print(timeit.timeit('sum(a)', setup, number=3))
print(timeit.timeit('b.sum()', setup, number=3))

Question: Why does sorting arbitrary distinct keys by comparisons require Ω(n log n) comparisons in the worst case? Derive the lower bound, without claiming it for every individual input.

Premise: For distinct keys, each comparison has two possible order outcomes. The deterministic comparison-sort model learns the ordering through these comparisons.

Because: by definition it may not inspect the values themselves, only their relative order

Premise: Its execution is therefore a binary decision tree: each internal node is a comparison, each branch an outcome, each leaf a final permutation the algorithm outputs.

Because: the algorithm is deterministic given the comparison results, so the results fully determine the path

Premise: The tree must have at least n! leaves, since any of the n! input orderings must be sortable and each needs a distinct output permutation.

Because: two different required permutations reached by the same path would mean one of them is produced wrongly

Premise: A binary tree with L leaves has height at least log₂(L), and the height is the worst-case number of comparisons.

Because: each level at most doubles the reachable leaves, so you need log₂(L) levels to reach L of them

Premise: So worst-case comparisons ≥ log₂(n!), and by Stirling's approximation log₂(n!) ≈ n log₂ n − n·log₂e, which is Θ(n log n).

Because: n! grows fast enough that its logarithm is dominated by the n log n term

Conclusion: This proves a worst-case Ω(n log n) comparison lower bound; merge sort supplies a matching O(n log n) upper bound. For n ≥ 2, at least n/2 factors in n! are at least n/2, so log₂(n!) ≥ (n/2)log₂(n/2); no appeal to timing is involved. Counting sort uses O(n+k) time for key range k, and radix sort O(d(n+b)) for d passes with radix b. They are linear only under suitable bounds on these extra parameters. A worst-case lower bound allows a linear best case on already-sorted data; CPython sorting exploits existing runs.

Name: Growth curve first, constants second, memory always

Picture: Ask one question of any piece of code: if the input is 10× bigger, what happens to the time? Unchanged → O(1). 10× → O(n). Slightly more than 10× → O(n log n). 100× → O(n²). Treat those ratios as heuristics for particular model functions, not proofs of a bound. Then ask a second question: what does memory do? An algorithm that is 2× faster but holds the whole input in RAM is not faster — it is a different algorithm with a hard ceiling, and it will fail at some input size rather than merely slow down.

• Add sequential work and sum the inner cost across loop iterations. For n iterations each scanning an n-sized list, the total is Θ(n²). Repeatedly copying a growing string can have the same sum; implementation optimisations or bounded inner sizes require a different count.

• Halving a single search interval yields logarithmic depth. Divide-and-conquer can visit many nodes: depth alone is not total work; sum costs across the recursion tree.

• Worst case is what you design for; average case is what you usually experience; the gap is where production incidents live — hash tables are O(1) average and O(n) worst, and adversarial or skewed keys can find that worst case.

• Constants matter below a workload-specific crossover. Measure before optimising complexity you only assumed was the bottleneck.

Trigger: Fire this model the moment you see: a loop inside a loop over the same collection · if x in some_list inside a loop · string built by += in a loop · a job whose runtime quadrupled when the data doubled · a query plan showing a nested-loop join over two large tables.

Decision: A job is too slow. Do you improve the algorithm's complexity, tune constants, or throw hardware at it?

Name: Reduce complexity

Gain: the only fix whose benefit grows with the data; turning O(n²) into O(n) can convert hours into seconds and, more importantly, stops the problem from returning next quarter

Cost: requires understanding and often restructuring the code; may need extra memory (hash tables, indexes); risks introducing correctness bugs in code that currently works

Pick: an operation-count analysis reveals avoidable superlinear work. Timing that grows faster than input is a clue, not a proof; paging, I/O and different data can also cause it

Name: Tune constants (vectorise, batch, cache)

Gain: large wins with no algorithmic change — moving a Python loop into NumPy or a columnar engine can be an order of magnitude, and it's usually a local, low-risk edit

Cost: a fixed multiplier, so it buys you time rather than headroom; the same wall returns at larger n; heavy vectorisation can hurt readability

Pick: the complexity is already right and the profiler shows time concentrated in a small hot region

Name: Scale out / bigger hardware

Gain: more capacity can address a working-set or parallel-throughput limit; scaling out may require partitioning, code changes and an operational rollout

Cost: linear cost forever, and it masks algorithmic problems — a quadratic algorithm on a cluster is still quadratic and will consume the new capacity in one growth cycle; distribution adds shuffle and coordination overhead of its own

Pick: the work is genuinely parallel and the per-node algorithm is efficient, or extra capacity is a measured temporary mitigation while the underlying issue is fixed

Verdict: Profile first; the bottleneck is regularly not where you assumed. Then fix complexity, then constants, then hardware — in that order, because each later step is cheaper to do and more expensive to keep.The trap worth naming: scaling out a quadratic algorithm looks like a fix and is a compounding bill. Under the idealised assumptions of perfect parallelism, no overhead and fixed runtime budget, doubling compute buys only sqrt(2) ≈ 1.414× the input for quadratic work, and you will pay for that capacity every day forever. Complexity problems are the only ones where an afternoon of thinking beats an unlimited budget.

(c) Hands-on · 25 min

You'll compare two pairs: linear versus binary membership search, then quadratic versus set-based duplicate detection. Each pair solves its own task; the four functions do not all solve the same problem. Save as bigo_demo.py in a fresh venv.

"""bigo_demo.py — see Big-O with your own eyes.
 
Run: python bigo_demo.py  # standard library only
"""
from __future__ import annotations
import bisect
import random
import time
from statistics import median
from typing import Callable
 
# ── implementations under test ────────────────────────────────────────────
def linear_search(xs: list[int], target: int) -> bool:
    """O(n) — walk until you find it."""
    for x in xs:
        if x == target:
            return True
    return False
 
def quadratic_dup_check(xs: list[int]) -> bool:
    """O(n²) — does xs contain a duplicate?  Purposely dumb version."""
    n = len(xs)
    for i in range(n):
        for j in range(i + 1, n):
            if xs[i] == xs[j]:
                return True
    return False
 
def linear_dup_check(xs: list[int]) -> bool:
    """O(n) average with bounded-cost hashing/equality; O(n) extra storage."""
    seen: set[int] = set()
    for x in xs:
        if x in seen:
            return True
        seen.add(x)
    return False
 
def binary_search(sorted_xs: list[int], target: int) -> bool:
    """O(log n) — requires sorted input."""
    i = bisect.bisect_left(sorted_xs, target)
    return i != len(sorted_xs) and sorted_xs[i] == target
 
# ── measurement harness ───────────────────────────────────────────────────
def time_it(fn: Callable[[], object], repeats: int = 5) -> float:
    """Return median wall-clock seconds across `repeats` runs."""
    samples: list[float] = []
    for _ in range(repeats):
        t0 = time.perf_counter()
        fn()
        samples.append(time.perf_counter() - t0)
    return median(samples)
 
def bench_search() -> None:
    print(f"{'n':>10}  {'linear':>12}  {'binary':>12}  {'ratio':>10}")
    for n in [1_000, 10_000, 100_000, 1_000_000]:
        xs = sorted(random.sample(range(10 * n), n))
        target = xs[-1]  # worst-case for linear
        t_lin = time_it(lambda: linear_search(xs, target))
        t_bin = time_it(lambda: binary_search(xs, target))
        ratio = t_lin / t_bin if t_bin > 0 else float("inf")
        print(f"{n:>10}  {t_lin*1e6:>10.1f}µs  {t_bin*1e6:>10.1f}µs  {ratio:>10.0f}x")
 
def bench_dup() -> None:
    print(f"\n{'n':>7}  {'quadratic':>14}  {'linear':>12}  {'ratio':>10}")
    for n in [100, 500, 2_000, 5_000]:
        xs = list(range(n))  # NO duplicates → worst case (full scan)
        t_q = time_it(lambda: quadratic_dup_check(xs), repeats=3)
        t_l = time_it(lambda: linear_dup_check(xs), repeats=3)
        ratio = t_q / t_l if t_l > 0 else float("inf")
        print(f"{n:>7}  {t_q*1e3:>12.2f}ms  {t_l*1e6:>10.1f}µs  {ratio:>10.0f}x")
 
if __name__ == "__main__":
    random.seed(42)
    print("── linear vs binary search ─────────────────────────")
    bench_search()
    print("\n── quadratic vs linear duplicate check ─────────────")
    bench_dup()

Run it (the full timing sizes are optional, not part of the bounded verification):

python bigo_demo.py

Illustrative output only — these numbers are not measurements from this review and do not establish ratios on your machine:

── linear vs binary search ─────────────────────────
         n        linear        binary       ratio
      1000       10.5µs         0.4µs         26x
     10000      105.2µs         0.5µs        210x
    100000     1050.1µs         0.6µs       1750x
   1000000    10501.0µs         0.7µs      15000x

── quadratic vs linear duplicate check ─────────────
      n     quadratic        linear       ratio
    100         0.42ms       15.0µs         28x
    500        10.20ms       75.0µs        136x
   2000       164.10ms      300.0µs        547x
   5000      1030.20ms      750.0µs       1373x

What each block does

Anatomy of the benchmark

Name: linear_search vs binary_search

Desc: Binary search requires sorted input. Sorting once costs O(n log n); q lookups then cost O(q log n), versus O(qn) scans. The benchmark excludes preparation, so it does not show a one-query end-to-end speedup.

Name: quadratic_dup_check vs linear_dup_check

Desc: The set-based duplicate check trades O(n) auxiliary storage for O(n) average time under the hashing assumptions; the pair scan uses O(1) auxiliary storage.

Name: time.perf_counter()

Desc: A high-resolution monotonic performance counter on the target Python runtime. Inspect time.get_clock_info("perf_counter") for actual resolution; do not assume sub-microsecond accuracy.

Name: median(samples)

Desc: Not mean. Wall-clock has fat tails (GC, OS interrupts). Median is robust to outliers; a single 100ms hiccup won't distort your read.

Name: target = xs[-1]

Desc: Worst-case for linear search — last element means full scan. Best-case (first element) would flatter linear unfairly.

What to observe

ClassName: ml-4 list-decimal space-y-1

The sample ratios illustrate a possible pattern, not expected constants. Binary search performs a logarithmic number of comparisons; the pure-Python scan visits all n elements when the target is last. The implementations also have different interpreter/C overhead. Compare multiple sizes and repetitions; record the input distribution, preparation boundary and memory costs alongside timings.

Exercise: compare measured growth with an analytically derived bound. Finite timings are observations, not a proof of asymptotic complexity.

Hint: Record several sizes and compare against counts you derive from the loops. A log curve is not a power law with a universal exponent 0.05; fitted slopes depend on the size interval and timer overhead. For positive samples use log-log plots as diagnostics, not proof.

Add a third algorithm and predict its shape before measuring:

def three_sum_naive(xs: list[int], target: int) -> bool:
    """O(n³) — do any three elements sum to `target`?"""
    n = len(xs)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if xs[i] + xs[j] + xs[k] == target:
                    return True
    return False

Predict on a no-solution input so no early return occurs: exactly C(n,3) triples are checked. C(200,3)/C(100,3) ≈ 8.122, approaching 8 as n grows; an early matching triple can instead return immediately. Wall time need not equal that count ratio. Use small n for a bounded check, and separate the count derivation from timing.

(d) Production reality · 15 min

Hidden multiplicative work in a service

Illustrative design, not the earlier attributed Discord incident: scanning c channels for each of u members visits uc pairs. An index keyed by the actual query can change the read path, but it costs build/storage/update work and must preserve permissions and freshness. A sorted array offers O(log n) search and O(n) insertion; a balanced tree offers O(log n) updates. Those are different designs. Measure tail latency and write overhead before declaring a service improvement; the former company/date/p99 numbers were unsupported.

Preserve the deduplication contract

List membership inside a growing loop can produce n(n−1)/2 equality comparisons for distinct inputs. A set changes average lookup cost, but returning a set also discards order. Keep an output list if first-occurrence order matters:

def dedupe_first(items):
    seen = set()
    out = []
    for item in items:
        if item not in seen:
            seen.add(item)
            out.append(item)
    return out

This requires hashable items with consistent stable equality/hash semantics. Average time is O(n), with O(k) set space plus O(k) output for k distinct items; hostile hashes can degrade it. A list-based oracle preserves order too and can validate small cases independently. Unhashable lists require a different key policy, not silently converting arbitrary objects.

Cache locality and memory accounting

A contiguous numeric buffer offers predictable sequential accesses; a pointer-based tree may visit scattered nodes. Python lists themselves store references, so do not assume their element objects form one packed numeric array. Neither representation universally wins at a specific n. Time the actual queries, including index construction if it belongs to the operation. Distinguish input storage from auxiliary memory: pair duplicate detection uses O(1) extra state, the set algorithm O(n), and recursive search also has a stack. Materialising all n-element permutations needs Θ(n·n!) output slots, regardless of clever generation.

Where this shows up in the rest of the plan

Root: Big-O is the currency of every performance conversation

Application: Discrete math

Desc: Combinatorics tells you when n! or 2ⁿ enumerations are hopeless — and when to prune.

Application: Data structures

Desc: Hash tables, heaps, tries — you'll internalise the complexity table.

Application: Algorithms

Desc: Sorts, binary search, DP — every one comes with a Big-O and a use case.

Application: Query planning

Desc: Databases run cost-based optimizers — every operator has its own Big-O.

Application: Caching

Desc: Trading memory (space) for latency (time) is the space/time trade-off at architecture scale.

Application: System design

Desc: Back-of-envelope capacity math — QPS, storage, bandwidth — is applied Big-O on real hardware.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — click each to reveal

Q: What does O(n) actually mean, in plain English?

A: O(n) is an asymptotic upper bound by a constant multiple of n beyond some size. Θ(n) is the tighter statement of linear growth; O(n) also includes constant-time functions.

Q: What's the Big-O of for x in xs: for y in xs: if x == y: ...?

A: If both loops traverse all n items without early exit and equality has bounded cost, there are n² comparisons: Θ(n²). Expensive equality or early termination changes the count model.

Q: Why is binary search O(log n) and not O(n)?

A: Each iteration halves the search space. After k steps you've reduced n items to n/2^k. Solving n/2^k = 1 gives k = log₂ n. Doubling n adds ONE more step, not doubles the steps.

Q: You have if x in some_collection in a hot loop. When is it O(1) and when is it O(n)?

A: Set/dict membership averages O(1) under well-distributed bounded-cost hashing/equality and can be O(n) with collisions. List/tuple membership needs up to n equality tests. For strings, a one-character search scans the text; substring search has a separate needle length and algorithm, so do not collapse all string searches to that same model.

Q: What is amortised complexity? Give one example.

A: Amortization bounds the total cost over a sequence, not a probability distribution. CPython lists overallocate capacity rather than necessarily doubling it; a resize can copy O(n) references.

Q: Sort these by growth rate, slowest → fastest at large n: n, log n, n log n, n², 2ⁿ, 1.

A: 1 < log n < n < n log n < n² < 2ⁿ. (Constants like 1 don't grow at all; exponentials eventually beat everything polynomial.)

Q: Why can an O(n²) algorithm actually be faster than an O(n log n) algorithm in practice?

A: Small n (constants dominate); cache-friendly memory access patterns (contiguous arrays beat pointer-heavy trees); simpler inner loops (better branch prediction, SIMD). Big-O only tells the asymptotic story.

Q: What's the Big-O of the naive fibonacci function fib(n) = fib(n-1) + fib(n-2)?

A: O(2ⁿ) is a valid loose upper bound. With base cases n=0,1, the exact number of calls is 2F(n+1)−1, giving Θ(φⁿ), where φ=(1+sqrt(5))/2; it is not roughly 2ⁿ leaves. Memoisation uses O(n) states/additions and O(n) stored values in a unit-cost model. Python Fibonacci values grow in bit length, so big-integer arithmetic/storage costs require a separate analysis.

Q: How would you argue Big-O to a coworker without a whiteboard?

A: Timing several sizes can reveal suspicious growth but does not prove a bound. Derive a count from the loops/data structure and use measurements as a falsification check.

Q: Stretch — you have a list of 10 million (user, timestamp) events and want the most common user in the last hour. Design an O(n) solution, then discuss when you'd choose an O(n log n) alternative.

Stretch: true

A: Fix one reference time now and the window (now−3600, now]. In one pass count qualifying hashable user IDs, then take top-1 in O(k) for k qualifying users: O(n) average total and O(k) auxiliary space under bounded-cost hashing. Return None for no events and define a tie policy (for example first encountered). Alternatively sort/index timestamps once in O(n log n), use two binary searches for both bounds and count w events in the slice: O(log n + w) average per query, plus O(k) counting space (and O(w) if the slice is copied). Repeated large overlapping windows still repeat work; an index alone does not make top-user queries logarithmic.

Explain-out-loud test

1. What does O(n²) mean in plain language, and what code shape produces it? (one sentence, one code shape)
2. Why does binary search require a sorted list, and what's its complexity? (name the two)
3. When is Big-O insufficient to predict wall time, and what should you measure? (name one situation, one action)

What comes next

Next: S016 · Discrete math.

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Explain-out-loud answer guide

1. O(n²) is an eventual upper bound by a fixed multiple of n²; a full constant-cost pair scan gives a tight example.
2. Sorted order permits discarding half the candidates after a comparison; otherwise the discarded side could hold the target. Binary search takes O(log n) comparisons, excluding preparation.
3. A small cache-friendly scan can outperform an indexed lookup once construction and constants are counted. Measure the end-to-end workload and memory without claiming the timing proves the asymptotic bound.

Corrective source notes

• Sorting Techniques — Python 3.14.8 documentation — Python sorting preserves the order of elements that compare equal. Checked 2026-10-07.

Additional primary references: NIST asymptotic definition, bisect performance notes, SortedContainers scaling, CPython 3.12 list allocation, CPython sorting design.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.