Pebellslearn by building
0%
RoadmapsMatrixCoursesSandboxSign in
Analysis II: Recurrences, Amortisation & Randomness  ›  Capstone Project

Capstone — the Tunebox Cost Lab

45 minMeasure what code really costs, fit a curve to the counts, and check it against the bound you proved
You're building a piece ofTunebox — the cost lab
This piece — fit_exponent(): Fits a power law to measured counts and reports the exponent.
Scenario Before Tunebox launches in a new country with ten times the listeners, the team runs every feature through the cost lab: measure, fit, compare with the proof, and find which feature breaks first.
Your task
Build fit_exponent(ns, counts). Given input sizes and the operation counts measured at them (all positive), return the least-squares slope of log(count) against log(n), rounded to 2 decimal places. Example: fit_exponent([10, 20, 40, 80], [100, 400, 1600, 6400]) → 2.0.

Capstone — the Tunebox Cost Lab

In short: instrument a function with a counter on its dominant operation, measure it at sizes that double, and the growth rate falls out of the ratio between neighbouring counts (×2 linear, ×4 quadratic). For a precise exponent, take logs of both n and the count: on a log-log plot a power law a·n^b becomes a straight line whose slope is b. The lab then checks that slope against the bound you proved on paper — and settles the n log n vs n^1.1 ambiguity by dividing the counts by each candidate model and seeing which one leaves a flat line.

A log-log plot of four measured points on a straight fitted line; the slope, read as rise over run, is the exponent b in c ≈ a·n^b

You now have two ways of knowing what code costs. On paper: read a recurrence off the code, solve it with a recursion tree, account for spikes with a bank of tokens, average over random pivots. In the machine: count the operations while the code runs. Each one checks the other. A proof with a slip in it disagrees with the count, and a count taken on an unlucky input disagrees with the proof.

The capstone puts them together in one instrument. The cost lab takes a function from sections 1 to 6, runs it on inputs of growing size, counts its real operations, fits a curve to the counts, and reports the exponent. You then compare that exponent with the bound you derived.

Step 1: instrument

Timing with a stopwatch measures your laptop. Counting measures the code. Pick the operation that dominates, the one inside the innermost loop, and add a counter there. For insertion sort from section 3 that is the shift:

python

A reversed list of four needs 6 shifts, a sorted one needs none. Which input you measure on matters as much as how you count, so the lab always states it: worst case (reversed), best case (sorted), or a seeded random input for the average.

Step 2: sweep n by doubling

Measure at n, 2n, 4n, 8n. Doubling makes the growth rate readable straight off the ratio between neighbouring counts: about 2 means linear, 4 means quadratic, 8 means cubic, and slightly more than 2 means n log n.

What does this print?
counts = [120, 496, 2016, 8128]
ratios = [round(counts[k + 1] / counts[k], 1) for k in range(len(counts) - 1)]
print(ratios)

Here is the lab's sweep running on your insertion sort, filling in its results table as it goes. Each row is one size; the last column is the doubling ratio. Swap in a different function: replace the body of measure with your merge sort's write count or a BFS on a bigger grid, and watch the ratio column change.

your code, drawn · grid

Your sweep, one row per size. A ratio settling at 4 says quadratic before any curve is fitted.

Step 3: fit a power law

Ratios are easy to read, but noisy data needs a single number. If the cost is c(n)≈a⋅nbc(n) \approx a \cdot n^b, taking logarithms turns it into a straight line:

log⁡c=log⁡a+b⋅log⁡n\log c = \log a + b \cdot \log n

So plot log⁡c\log c against log⁡n\log n and the slope is the exponent. With two measurements, the slope is just rise over run. Step through it:

step through it
1import math
2n1, c1 = 64, 2016
3n2, c2 = 256, 32640
4rise = math.log(c2) - math.log(c1)
5run = math.log(n2) - math.log(n1)
6b = rise / run
7print(round(b, 2))

With many measurements, fit the best straight line by least squares, the same method as in regression:

b=∑(Xi−Xˉ)(Yi−Yˉ)∑(Xi−Xˉ)2,Xi=log⁡ni, Yi=log⁡cib = \frac{\sum (X_i - \bar X)(Y_i - \bar Y)}{\sum (X_i - \bar X)^2}, \qquad X_i = \log n_i,\ Y_i = \log c_i

A slope is only meaningful on the log scale. Fit the raw numbers and you get the wrong kind of answer:

broken — fix it

The counts are exactly n², so the fitted exponent should print 2.0. It prints 92.61, the slope of the raw counts: "about 93 more steps per extra item", which is not an exponent at all.

Step 4: the verdict, and why n log n looks like n^1.1

Run the lab on four of your functions, each on inputs chosen to match the bound you proved:

python

Insertion sort comes out near 2, the append and BFS near 1. Merge sort comes out around 1.18, which is not a sign that it is n1.18n^{1.18}. Over a range of sizes, nlog⁡nn \log n looks like a power law whose exponent is a little above 1, and the extra part shrinks slowly as the range moves to larger n. An exponent alone cannot tell nlog⁡nn \log n from n1.1n^{1.1}. The lab settles it the other way round: fit each candidate model and keep the one that leaves the smallest error.

What does this print?
import math

ns = [1024, 2048, 4096]
counts = [n * int(math.log2(n)) for n in ns]
print([round(c / n, 1) for c, n in zip(counts, ns)])

The same division, done on merge sort's real counts:

watch it move · grid

Divide the counts by each candidate model. The right model leaves a constant; the wrong one leaves a trend.

Merge sort's measured writes at five sizes, each double the last. 3 by 5 table. At row 0, column 0 — value 384. 5 of 15 cells filled.

1 / 3

That is the boss exercise: compare the models n, n log n and n² directly against the counts, rather than trusting one exponent.

❓ Cross-question — "Why not just time it?" Timings mix in the interpreter, the cache, the garbage collector and whatever else the machine is doing, and they differ between runs. They are the right tool for "is it fast enough?" Counts are the right tool for "does it grow the way I proved?" The lab uses counts so that the same code gives the same answer every time.

Idioms & real-world patterns

Measure the worst case on purpose

Random inputs show the average. Bugs in production come from the worst case: the sorted chart, the listener with a million followers. Include the input your proof says is worst, and check that the count matches.

Stop a sweep before it hurts

Doubling grows fast. Put a budget on the total operations counted and stop the sweep when the next size would exceed it. A quadratic function at n = 10⁶ takes a lot longer than you want to wait.

⚡ Advanced — residuals

After fitting, compute each measurement's relative error against the fitted curve. If the errors drift steadily in one direction with n, the model has the wrong shape, however good the exponent looks. That drift is the signal that separates nlog⁡nn \log n from a power law.

Quick practice

What does this print?
counts = [100, 800, 6400, 51200]
ratios = [round(counts[k + 1] / counts[k], 1) for k in range(len(counts) - 1)]
print(ratios)
broken — fix it

The counts triple... no, they go ×8 each time n doubles, so the ratios should read [8.0, 8.0, 8.0]. This prints [0.12, 0.12, 0.12] — correct in spirit (constant, so still a clean power law) but inverted, which would be misread as "shrinking" work.

🎯 Your turn

Write fit_exponent(ns, counts), the lab's curve fitter. Given sizes and the operation counts measured at them (all positive), return the least-squares slope of log(count) against log(n), rounded to 2 decimal places.

  • fit_exponent([10, 20, 40, 80], [100, 400, 1600, 6400]) → 2.0
  • fit_exponent([100, 200, 400], [300, 600, 1200]) → 1.0

Then use the exercises to build the rest of the lab: doubling ratios, instrumented specimens, a model chooser, and the report that says which Tunebox feature breaks first.

Press ▶ Run, tap the Live App try chips, and hit ✓ Check.

Practice — level up

0/6 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upRead the ratios

The lab measured counts at n, 2n, 4n, … Write doubling_ratios(counts) returning each count divided by the one before it, rounded to 2 decimal places. doubling_ratios([120, 496, 2016]) → [4.13, 4.06].

complexitybig-o
DrillInstrument insertion sort

Instrument your section 3 insertion sort. Write insertion_shifts(items) returning how many times an item is shifted one place to the right while sorting a copy of items ascending. Equal items are not shifted past each other.

insertion-sortcomplexity
BuildInstrument BFS

Instrument your section 5 breadth-first search. graph maps each listener to the list of listeners they follow (a listener with no key follows nobody). Write bfs_checks(graph, start) returning how many times the search looks at a follow — once per entry in the follow list of every listener it dequeues.

bfsaggregate-analysis
BossWhich curve fits?

A fitted exponent can't tell n log n from n^1.1. Compare the candidate models directly. For each model g in the order "n", "n log n" (using math.log2), "n^2": fit a·g(n) with a = Σ c·g / Σ g², then score it by Σ ((c − a·g) / c)². Write best_model(ns, counts) returning the name of the lowest-scoring model (the earlier one on a tie). All n ≥ 2 and all counts are positive.

complexityregressiondivide-and-conquer
CapstoneWhich feature breaks first?

The lab has measured several Tunebox features. Each profile is {"name", "ns", "counts"}. For each, fit count ≈ a·n^b by least squares on the logs (b is the slope; a = e^(mean(log c) − b·mean(log n))), then find the smallest power of two n (1, 2, 4, …) whose predicted count a·n^b is greater than budget. Write first_to_break(profiles, budget) returning the name that breaks at the smallest n (the one listed first on a tie).

complexityregressionbig-o
ExplainWhen the count disagrees with the proof

The lab fits merge sort's write counts for n = 64 to 1024 and reports an exponent of 1.18. A teammate says: "so merge sort is really O(n^1.18), not O(n log n)". Explain why that conclusion is wrong, and how the lab should decide between the two.

fit_exponent.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
fit_exponent(ns, counts) → floatThe fitted exponent b in count ≈ a·n^b, rounded to 2 places.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.