Asymptotic Analysis: Big-O, Omega, Theta

Notes 01 ended with a promise: that two correct procedures could be compared without running either one. These notes keep it. Over two sessions we build the vocabulary of growth — Big-O, Omega, Theta — learn to read the cost of a loop straight off its structure, and then look deliberately at where the clean theory and the physical machine part ways. That last gap is not a footnote; it is what Project 1 asks you to measure.

Session planHow we will spend the two sessions

Section 1Growth, not seconds

Run the linear search from Notes 01 in Python, on a laptop, over a list of a million entries, and a typical unlucky query takes around thirty milliseconds. Port the same procedure to C++ and run it on a rented server and the same query finishes in well under one. Nothing about the algorithm changed — every element still gets inspected once, in order. The thirty-fold difference is real, and it belongs entirely to the machine, the language, and the compiler. Which raises an uncomfortable question: if seconds can swing by a factor of thirty while the algorithm holds perfectly still, what exactly were the seconds measuring?

They were measuring the implementation. If we want a number that describes the algorithm — the thing that survives translation between languages and machines, the thing this course is actually about — we have to count something more honest than time. So we count steps.

Let us count once, carefully, so you see how it works — and why we will never again do it this carefully.

def total(A):
    """Return the sum of the elements of A.

    Precondition:  elements of A support +.
    Postcondition: result equals the sum of all elements (0 if A is empty).
    """
    s = 0                    # 1 step:   one assignment
    for x in A:              # n+1 steps: n advances + 1 exhausted-check
        s = s + x            # 2n steps:  n additions + n assignments
    return s                 # 1 step

Add it up: T(n) = 3n + 3. Now watch how little loyalty that exact expression deserves. Count the loop bookkeeping differently — perfectly defensibly — and you get 4n + 2, or 2n + 3. Run it on hardware where an addition costs twice what an assignment costs and the weights shift again. Every one of those is a different function, and every one of them doubles when n doubles. The constants are artifacts of the counting convention. The shape — linear — is a fact about the algorithm.

That is the deal asymptotic analysis offers, and it is a good one. We give up the constants, which were never ours to know, and keep the growth, which no machine can take away.

Section 2Big-O, Omega, Theta

We need a way to say "grows no faster than," "grows at least as fast as," and "grows exactly like" that is precise enough to prove things with. Here are the three definitions the rest of the course stands on. They reward slow reading — every phrase is load-bearing.

In English: past some point, and up to a constant factor, g is a ceiling for f. The two constants are where the philosophy of §1 becomes mathematics. Choosing c says "I do not care about constant factors" — you may raise the ceiling by any fixed multiple. Choosing n₀ says "I do not care about small inputs" — any finite prefix is exempt. What is not negotiable is the tail: from n₀ onward, the inequality must hold for every single n, forever. A ceiling that leaks even occasionally is not a ceiling.

The picture to carry: O presses down from above, Ω presses up from below, and Θ says the two presses meet — g captures f's growth exactly, up to constants. A finished analysis states a Θ whenever it can; it retreats to O when only a ceiling is known.

Proving one — the certificate

A Big-O statement is an existence claim, and existence claims are proved by producing the thing that exists. The pair (c, n₀) is called a certificate, and exhibiting one, plus a line of algebra, is the entire proof.

Claim: 3n + 8 ∈ O(n). Certificate: c = 4, n₀ = 8. Check: for every n ≥ 8 we have 8 ≤ n, so 3n + 8 ≤ 3n + n = 4n. Done. Notice the certificate is not unique — c = 11, n₀ = 1 also works, since 8 ≤ 8n for n ≥ 1 gives 3n + 8 ≤ 11n. There is no "best" certificate and no credit for a tight one; any valid pair settles the claim.

Disproving flips the quantifiers, which makes it harder in exactly the way it should be: to show n² ∉ O(n) you must defeat every certificate. So take any c and n₀ someone offers, and pick n = max(n₀, c + 1). Then n² = n·n > c·n. Whatever ceiling they raise, n² crosses it. That universal defeat — no c works, ever — is what "not in O" means.

The demonstration below makes the quantifier game physical. Pick a claim, then hunt for a certificate with the two sliders. For the true claims a correct (c, n₀) turns the verdict green; for the false ones the page finds a crossing point no matter what you choose — watch how the counterexample simply moves further out as you raise c.

Certificates are also checkable by machine — over a finite grid, which is evidence rather than proof, but excellent for catching wrong guesses before you commit algebra to paper. This function is worth keeping in your Project 1 toolbox:

def certifies(f, g, c, n0, N=10**6):
    """Check that f(n) <= c * g(n) for all n0 <= n <= N.

    Precondition:  c > 0 and n0 >= 1.
    Postcondition: True iff the inequality held on the whole grid.
    Not promised:  anything about n > N. A grid check is evidence,
                   not a proof — the proof is the algebra.
    """
    return all(f(n) <= c * g(n) for n in range(n0, N + 1))

# The worked claim from above:
#   >>> certifies(lambda n: 3*n + 8, lambda n: n, c=4, n0=8)
#   True

Section 3The growth-class bestiary

In principle any function can sit inside a Θ. In practice, a handful of shapes cover nearly everything you will meet this semester, and you should know them the way you know multiplication tables — instantly, and with a feel for what each one costs at scale. The table prices each class at n = 10⁶ on a machine doing 10⁸ elementary operations per second, which is a fair cartoon of interpreted Python.

Numbers make the classes vivid; knowing where each one comes from makes them usable, because you start recognizing the shape in code before you analyze anything.

• Θ(log n) appears whenever each step discards a constant fraction of the candidates. A billion items survive only about thirty halvings — logarithms are the reason "a billion" can be a small number.
• Θ(n) is the price of looking at everything once. For any problem whose answer can depend on every element, it is also a floor — you cannot answer about data you never read.
• Θ(n log n) is log work per element, or halve-and-recombine. It is the signature of good sorting, and — as Week 5 will prove — the best any comparison sort can do.
• Θ(n²) is every pair. Utterly fine at n = 1,000; an outage at n = 10⁶. Most real-world performance disasters are an accidental n² hiding in innocent code — §4 shows the usual hiding places.
• Θ(2ⁿ) is every subset: each new element doubles the work. Θ(n!) is every ordering, and grows faster still. These classes are why Weeks 14–15 exist — when a problem forces you here, the interesting question stops being "how do I compute it" and becomes "what do I settle for instead."

Before you drive the demonstration, one deliberately extreme claim to test against it: fix any constants you like — say 10,000·n against 0.0001·2ⁿ, a hundred-million-fold head start for the exponential's rival to squander. The exponential still loses the race, and "eventually" arrives near n ≈ 32, not at some safely theoretical horizon. Constants decide who wins early. The class decides who wins.

Section 4Analyzing loops

The definitions give us a language. Now we need the calculus — the small set of rules that reads a growth class off the structure of code, without counting individual steps. There are five, and together they analyze the overwhelming majority of the code you will write this semester.

One loop — and a friend from last week

def maximum(A):
    """Return the largest element of A.  (Specified and proved in Notes 01.)"""
    m = A[0]
    for i in range(1, len(A)):
        if A[i] > m:
            m = A[i]
    return m

The body is a comparison and possibly an assignment — Θ(1) by rule 1. The loop runs n − 1 times — rule 3 gives (n − 1) · Θ(1) = Θ(n). The two statements outside the loop add Θ(1), which rule 2 discards. Θ(n), and notice the division of labor across two weeks: in Notes 01 you proved this loop correct; today it took one more line of thought to price it. That pairing — argue, then count — is what a complete analysis looks like in your project reports.

Loops in sequence — the largest term wins

def span(A):
    """Return max(A) - min(A) for non-empty A."""
    lo = A[0]
    for x in A:          # pass 1: Θ(n)
        if x < lo:
            lo = x
    hi = A[0]
    for x in A:          # pass 2: Θ(n)
        if x > hi:
            hi = x
    return hi - lo       # total: Θ(n) + Θ(n) = Θ(n)

Two passes is Θ(2n) = Θ(n) — the 2 is a constant, and Θ absorbs it. Students often feel this should "count double." It does count double in seconds, and §6 is where seconds get their due; in growth terms, a program that reads its input twice scales exactly like one that reads it once. Contrast rule 2's other face: had the second pass been a nested Θ(n²) block, the whole function would be Θ(n²) and the linear pass would vanish from the answer entirely.

Nested loops — multiply

def has_duplicate(A):
    """Return True iff some value occurs at two distinct indices of A."""
    n = len(A)
    for i in range(n):
        for j in range(n):          # inner bound ignores i → multiply
            if i != j and A[i] == A[j]:
                return True
    return False

The inner loop runs n times regardless of i, so rule 3 applies twice: n iterations of an n-iteration loop with a Θ(1) body — n · n · Θ(1) = Θ(n²) in the worst case (no duplicate, so the early return never fires and every pair is examined). Multiplication is legitimate here precisely because the inner bound ignores the outer variable. When it does not, rule 4 takes over.

Triangular loops — sum, then simplify

The version above compares each pair twice, and compares elements with themselves. The natural fix starts j after i:

def has_duplicate(A):
    """Return True iff some value occurs at two distinct indices of A."""
    n = len(A)
    for i in range(n):
        for j in range(i + 1, n):   # inner bound depends on i → sum
            if A[i] == A[j]:
                return True
    return False

Now the inner loop runs n−1−i times, which changes with i, so we write the sum and close it — Gauss's classic:

Half the comparisons of the square version — a real saving your benchmark will see — and exactly the same class. The ½ is a constant and the −n/2 is a lower-order term; Θ discards both. This example is worth internalizing as the boundary line between the two kinds of improvement this course cares about: constant-factor improvements, which engineering delivers, and class improvements, which only a different algorithm delivers.

The halving loop

Binary search, met informally last week as the phone-book strategy, is the canonical rule-5 loop — it needs sorted input, and repays that precondition with logarithmic work:

def binary_search(A, target):
    """Return an index i with A[i] == target, or None if absent.

    Precondition:  A is sorted in non-decreasing order.
    Postcondition: result is a valid index of target, or None if
                   target does not occur in A.
    Not promised:  which occurrence is returned on duplicates.
    """
    lo, hi = 0, len(A) - 1
    while lo <= hi:
        # invariant: if target is in A, it lies in A[lo .. hi]
        mid = (lo + hi) // 2
        if A[mid] == target:
            return mid
        elif A[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return None

Each iteration does Θ(1) work and then discards half the live range: after k iterations at most n/2^k candidates survive. The loop ends by the time n/2^k drops below 1, i.e. after at most ⌊log₂ n⌋ + 1 iterations — O(log n) worst case. (Worst case, note — if the first midpoint is the target it exits after one comparison, a distinction §5 makes precise.) The invariant comment, meanwhile, is Notes 01 pulling its weight: it is exactly what you would use to prove the loop correct, and stating it is how off-by-one bugs in lo/hi get caught before the debugger opens.

The hidden loop

def dedupe(A):
    """Return the elements of A in order, first occurrences only."""
    out = []
    for x in A:              # n iterations…
        if x not in out:     # …but this line is a LOOP: a linear scan of out
            out.append(x)
    return out

The body looks Θ(1) — one membership test, one append. But x not in out on a Python list is a linear scan wearing a keyword's clothing: it walks out element by element. When A has no duplicates, out has i elements at step i, the test costs Θ(i), and the total is our triangular sum again: Θ(n²) from code with only one visible loop.

Analysis paying rent — prefix averages

To close, an example where analysis does not just describe code but improves it. Task: given daily readings, produce the running average — B[i] is the mean of A[0..i]. The direct translation of that sentence into code recomputes each prefix sum from scratch:

def prefix_averages_naive(A):
    """Return B with B[i] == mean(A[0..i])."""
    B = []
    for i in range(len(A)):
        s = 0
        for j in range(i + 1):     # re-adds the whole prefix, every time
            s += A[j]
        B.append(s / (i + 1))
    return B

def prefix_averages(A):
    """Return B with B[i] == mean(A[0..i]).  Same spec, one pass."""
    B, s = [], 0
    for i, x in enumerate(A):
        s += x                     # carry the running sum forward
        B.append(s / (i + 1))
    return B

The naive version is the triangular sum — 1 + 2 + ⋯ + n = Θ(n²). The second version notices that prefix i's sum is prefix i−1's sum plus one element, carries it forward, and runs in Θ(n). Same specification, same outputs, and at n = 10⁶ the difference is roughly three hours against a hundredth of a second. Hoisting recomputed work out of a loop is arguably the single most common genuine performance win in real codebases, and you find it by doing exactly what this section did: write the sum, look at it, and ask which additions were already done.

Section 5Best, worst, and average case

Here is a question §4 quietly stepped around: what is "the" running time of linear search? If the target sits in the first slot, one comparison. If it sits in the last slot, or is absent, n comparisons. Both answers are honest — they are answers about different inputs of the same size. "Input size n" is not one input; it is a whole population, and the algorithm's cost varies across it.

For linear search over n elements: the best case is 1 comparison (target first). The worst case is n (target last, or absent). For the average, an assumption must go on the record — say the target is present, and equally likely to be in any of the n positions. Then each position i costs i comparisons and the expectation is

— about half a full scan, and still linear. Notice what the calculation consumed: a distribution. Change the assumption (searches often repeat popular keys; the target is sometimes absent) and the answer changes. Best and worst need no such assumption, which is a large part of their appeal.

Unless a course document says otherwise, "the running time" means the worst case, and there are three principled reasons the field settled there. First, it is a guarantee — a promise to every user on every input, which is the shape of promise real systems need. Second, it is adversary-proof: production inputs are not uniformly random, and are sometimes chosen by someone hostile. Third, it composes: worst-case bounds on parts add up to a worst-case bound on the whole, while average-case bounds only compose when the distributional assumptions survive the composition — which they routinely do not.

None of that makes the average case unimportant — it makes it expensive, because it must carry its distribution visibly. Two of this course's best stories are average-case stories told properly: quicksort (Week 4), whose worst case is Θ(n²) yet which dominates practice, and hashing (Week 6), whose constant-time reputation is an expected-time claim resting on assumptions Project 2 will make you state.

Section 6The model and the machine

Everything above happened inside the RAM model, where memory is uniform and every step costs one. Real machines are pricklier. A memory access that hits L1 cache costs a nanosecond; one that misses to main memory costs a hundred times that — so two Θ(n) traversals can differ enormously depending on access pattern. An interpreted Python statement costs tens of times its compiled equivalent, which is why sum(A) — the same Θ(n) as our total, but executed inside C — beats it by an order of magnitude. Allocation, branch prediction, vectorization: all real, and all constants. The model absorbs them, and the growth class survives untouched.

But constants decide real contests at real sizes. The classic example, which Project 1 has you reproduce: insertion sort is Θ(n²) and merge sort is Θ(n log n), yet insertion sort's constant is tiny — tight loop, no allocation, cache-friendly — while merge sort pays for recursion and copying. On real machines, insertion sort wins below n of a few dozen. That is not a violation of the theory; it is the theory, read correctly. Θ statements are about the endgame, and production libraries respect both truths at once: Timsort, the sort inside Python's own sorted(), is a merge sort that hands small runs to insertion sort.

The demonstration below is that contest reduced to its skeleton: algorithm A costs c₁·n log₂ n, algorithm B costs c₂·n². You control the constants; the page computes the break-even point n*. Try to make the crossover disappear.

Measuring honestly — a Project 1 preview

Project 1 — the Complexity Laboratory — asks you to implement algorithms, predict their curves with this week's tools, measure them, and explain every disagreement. Measurement has its own discipline, and sloppy benchmarks are how wrong conclusions get published. The rules we will hold your write-up to:

• Repeat, and report the median. A single timing is one sample from a noisy distribution — the operating system was doing other things. Medians shrug off the outliers that means absorb.
• Warm up before you time. First runs pay one-time costs: cold caches, lazy imports, frequency scaling spinning up.
• Vary n geometrically — 1,000, 2,000, 4,000, … — and plot on log-log axes. A polynomial Θ(nᵏ) becomes a straight line of slope k, and the exponent your machine actually delivers becomes something you read off a ruler.
• Hold the environment still: same machine, wall power, background load minimized, and say so in the write-up.
• Treat disagreement as the finding, not the failure. When the measured curve bends away from the predicted one, some assumption of the model broke — the cache, the interpreter, the allocator. Finding which is the interesting part, and it is the part the rubric weights most heavily.

import time, statistics

def bench(fn, arg, repeats=7):
    """Median wall-clock seconds for fn(arg) over several runs.

    Precondition:  fn is pure enough to rerun (no state carried between calls).
    Postcondition: result is the median of `repeats` timed runs, after one
                   untimed warm-up call.
    Not promised:  comparability across machines, power states, or days.
    """
    fn(arg)                              # warm-up, untimed
    times = []
    for _ in range(repeats):
        t0 = time.perf_counter()
        fn(arg)
        times.append(time.perf_counter() - t0)
    return statistics.median(times)

Section 7Before next session

Next week the code starts calling itself. Recursion gives us the most powerful design tool in the course — divide and conquer — and costing it requires a new instrument: the recurrence relation, plus a theorem that solves most of the ones arising in practice on sight. That is Notes 03.