The Doubling Experiment

6.1The question that replaces "is it fast?"

"Is my program fast?" is unanswerable — fast compared to what, on whose machine, with how much data? The useful question is:

This one question has a small number of possible answers, and each answer identifies a family of algorithms. You do not need mathematics to use it. You need a stopwatch, four input sizes, and a division.

Memorise two rows if you memorise nothing else: 2.0 is fine, 4.0 is a warning.

6.2Running the experiment

A reusable harness. Give it a function and a list of sizes, get a table with ratios.

import time

def time_it(func, arg, repeats=5):
    best = None
    for _ in range(repeats):
        start = time.perf_counter()
        func(arg)
        elapsed = time.perf_counter() - start
        if best is None or elapsed < best:
            best = elapsed
    return best

def doubling(func, start_n=10000, doublings=5):
    """Time func at n, 2n, 4n ... and print the ratio each time."""
    sizes, times = [], []
    n = start_n
    previous = None
    print(f"{'n':>9} {'seconds':>12} {'ratio':>7}")
    for _ in range(doublings):
        t = time_it(func, n)
        ratio = t / previous if previous else float('nan')
        print(f"{n:>9} {t:>12.5f} {ratio:>7.2f}")
        sizes.append(n); times.append(t)
        previous = t
        n = n * 2
    return sizes, times

Now try it on three functions with visibly different shapes:

def constant(n):                 # ignores n entirely
    return n * (n + 1) // 2

def linear(n):                   # one loop over n
    total = 0
    for i in range(n):
        total += i
    return total

def quadratic(n):                # loop inside a loop
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    return count

sizes_l, times_l = doubling(linear, start_n=100000)
sizes_q, times_q = doubling(quadratic, start_n=500, doublings=4)

You did not need to read the code to tell them apart. The ratio column did it: 2.0 versus 4.0. This is the core practical skill of the course, and you now have it.

How do you pick that starting size without guessing? Run the function once at a small n, look at the time, and scale up. If your shape is linear and n = 1 000 took 0.00001 s, then 0.05 s needs about 5 000 times more work, so start near n = 5 000 000. If the shape is quadratic, remember that the time grows with the square: a 100× longer run only needs a 10× bigger n. A quick pilot run saves you from either a wall of noise or a coffee break.

6.3Drawing the picture

A table convinces you; a plot convinces everyone else. Matplotlib is already installed in Colab.

import matplotlib.pyplot as plt

plt.figure(figsize=(6, 4))
plt.plot(sizes_l, times_l, marker="o", label="one loop")
plt.plot(sizes_q, times_q, marker="s", label="loop inside a loop")

plt.xlabel("input size n")
plt.ylabel("time (seconds)")
plt.title("Running time vs input size")
plt.legend()
plt.grid(alpha=0.3)
plt.show()

Every plot you hand in must have: axis labels with units, a title, and a legend if there is more than one line. A plot without labels is not evidence, it is decoration.

When the numbers are wildly different

If one curve is a million times taller than another, the small one flattens into the axis. Switch both axes to logarithmic scale and each straight line's slope tells you the growth: slope 1 is linear, slope 2 is quadratic, flat is constant.

plt.xscale("log")
plt.yscale("log")

6.4Reading — and measuring — the slope

Why does a log–log plot turn a power law into a straight line? The following algebra applies to a fixed constant times n to a fixed power. Other models, including n log n, need not become exactly straight:

T = c · n^k

Take the logarithm of both sides and the multiplication becomes addition, the power becomes a multiplier:

log T = log c + k · log n

That is the equation of a straight line — log n along the bottom, log T up the side, a slope of exactly k, and the constant c only shifting the line up or down without tilting it. So on log–log axes the power becomes the slope, and the machine-dependent constant becomes an offset you can ignore. Constant → slope 0 (flat). Linear → slope 1. Quadratic → slope 2. Cubic → slope 3.

You do not have to eyeball the slope. numpy.polyfit fits the best straight line through your logged points and hands you the slope as a number:

import numpy as np

def loglog_slope(sizes, times):
    """Best-fit slope through the points on log-log axes."""
    slope, intercept = np.polyfit(np.log(sizes), np.log(times), 1)
    return slope

print(f"linear    slope = {loglog_slope(sizes_l, times_l):.2f}")
print(f"quadratic slope = {loglog_slope(sizes_q, times_q):.2f}")

This is the ratio column's more grown-up cousin. The ratio reads growth from two points at a time; a fitted slope summarizes all your points. Outliers and systematic effects can still bias it. Inspect the samples and residual pattern as well as the slope; a straight-line fit is evidence about the measured range, not a complexity proof.

6.5When the ratio column misleads you

The ratio is a wonderful tool, but a tool you trust blindly will eventually cut you. Three situations make honest ratios lie about the pattern.

1. The starting size is too small

Below the noise floor the ratio is meaningless — it wanders 0.6, 1.9, 0.4 with no shape at all, because you are timing interruptions, not your algorithm. This is the number one cause of a "weird" ratio column, and the fix is always the same: grow the starting size until the first run clears roughly 0.01–0.1 seconds, then read again.

2. n log n looks like a drifting 2

The most subtle case. A sorting run does not give a clean 2.0 or 4.0 — it gives a ratio just above 2 that slowly drifts downward towards 2 as n grows:

The reason: doubling n doubles the loop (that is the 2), and the log n factor adds only a sliver more each time — a sliver that shrinks as n grows, because the logarithm grows ever more slowly. Read too high a starting size and you might call it linear; read too low and you might call it quadratic. The honest verdict is "just above 2 and falling slowly", which is consistent with an n log n model. A fitted slope (§6.4) depends on the input range and is not a fixed class identifier. For exact T(n) = n log₂ n, T(2n)/T(n) = 2 + 2/log₂ n.

3. Memory effects can inflate a linear ratio

A perfectly linear loop can show ratios above 2 once the data grows too big to sit in the CPU's fast cache. Suddenly each item costs a slow trip to main memory, and the time per item rises just as n rises. The algorithm did not change class; the hardware changed gear. If a clean O(n) function starts posting 2.3, 2.6 at very large sizes, suspect the cache before you rewrite the algorithm.

6.6Interpreting like a scientist

Every benchmark in this course ends with a short paragraph. Use this skeleton until it becomes automatic:

Worked example, for the quadratic run above:

"I timed the nested-loop counter at n = 500, 1 000, 2 000 and 4 000, five repeats each, taking the fastest. The time ratios were 3.99, 4.02 and 3.99, and a log–log fit gave a slope of 2.00. Four times the work for twice the data matches a loop inside a loop, which is exactly what the code does: the inner loop runs n times for each of the n outer passes. The 4 000 run took nearly a second, so background load on the shared Colab machine could have inflated it slightly. Extrapolating, n = 40 000 would be 100× the 4 000 time — about 80 seconds — which I would not want to run in a live report."

Reading the timing examples: displayed seconds and fitted slopes are illustrative output, not measurements from your machine. Run the experiment, retain the actual samples, and report the input and measurement conditions. Exact operation-count formulas are separate mathematical claims.

6.9Optional Studio Extension

6.10Words from this week