Project 1 — Measure, Predict, Confirm

“For which of you, desiring to build a tower, does not first sit down and count the cost, whether he has enough to complete it?” — Luke 14:28

Chapter: 1 — The Architect’s Question Due: End of Week 1 Submit: A link to your code — a public GitHub repository — containing your source, your data, your plot, and REPORT.docx. See Appendix A for the Python/git toolchain setup and the repo workflow. Allowed tools: Python 3, the standard library (time, gc, sys, tracemalloc), a plotting tool of your choice (matplotlib, a spreadsheet, or hand-drawn on graph paper), a non-AI editor, the textbook. Phase 1 (wk 1–8): AI is OFF. No assistants of any kind — not for the code, not for the prediction, not for the report. You cannot reason about a cost you have never personally paid, and you cannot direct an agent to choose well later if you let one do the counting for you now. (Phase 2 projects, wk 9–16, will require an agent-log.txt; this one forbids the agent entirely.)

The Setup

A small ministry runs a volunteer-built attendance and giving tracker. It has worked fine for three years on a laptop in the church office, holding a few hundred records. Now the regional office wants to merge twelve congregations into one system — tens of thousands of records, growing every week.

The volunteer who built it is nervous. “It’s fast on my machine,” he says, “but I have no idea what happens when the data gets big. Some of these reports take a noticeable second already, and we’ve only got four hundred people.”

You are the architect they called. You don’t have their full codebase yet — but you have four small programs that represent the shapes of operations their system performs, one program per complexity class. Before you touch their real code, you are going to do the thing the volunteer never did: count the cost before the tower is built. You will predict how each shape scales, measure it honestly, and write the one-page report that tells the ministry which operations will still be fine at fifty thousand records and which will quietly become a disaster.

The scale of the programs is tiny on purpose. The discipline — predict, measure, confirm — is identical whether n is four hundred or four hundred million. You are learning the move at a scale where you can see all of it at once.

Setup

A starter is provided in this chapter’s code/ folder:

• code/complexity_demos.py — five reference functions, one per complexity class, all runnable. Read them; they’re your subjects’ cousins.
• code/timing_harness.py — a complete, honest timing harness. Study it, but for the project you build your own (you did this in Rep 6).
• code/space_demo.py — sys.getsizeof and tracemalloc examples for the Medium tier.
• code/p1_starter.py — the scaffold you will finish. It contains the four subject programs (A, B, C, D) whose bodies you must not change, and a timing harness with TODOs for you to complete.

You will write:

• measure.py — your finished harness + experiment runner (start from p1_starter.py).
• data.csv — the table of numbers your experiment produced (program, n, best_ms).
• plot.png (or a clear hand-drawn/spreadsheet equivalent) — the curves.
• REPORT.docx — the one-page report. This is the real deliverable.

The Four Subjects

From p1_starter.py. Do not change their bodies — these are the programs whose scaling you are predicting.

• Program A — program_a(data): returns the middle element.
• Program B — program_b(data): sums every element.
• Program C — program_c(data): returns a sorted copy.
• Program D — program_d(data): counts equal pairs the naive way (a loop inside a loop).

Part of your job is to name the complexity class of each from the code alone, before you measure. One of A/B/C/D is O(1), one O(n), one O(n log n), one O(n²). Figure out which is which, in writing, before you run anything.

Learning Targets

By completing this project, you will demonstrate that you can:

• Read a small program and predict its Big-O from the code alone.
• Build an honest timing harness (warmup, repeat-and-minimum, GC paused, time only the work).
• Measure runtime across growing input sizes and read the ratio of the response to doubling n.
• Relate a measured curve back to its Big-O — and explain any gap between the two.
• (Medium) Measure space with tracemalloc/sys.getsizeof and articulate a time/space tradeoff.
• (Hard) Find a case where the measured behavior contradicts the apparent Big-O, and explain why the asymptotics lied at that scale.

Normal Tier

Goal: Predict, measure, and confirm the scaling of all four subject programs, and write the one-page report.

Required features

1. Written prediction, first. Before running anything, in REPORT.docx, name the Big-O of each of A/B/C/D and predict, in one sentence each, what its timing should do as n doubles (stay flat / barely grow / double / quadruple). Commit to it. This section must be written before your measurements — that’s the point of the exercise, and your report must show it (predictions in one section, results in the next).
2. An honest harness. Finish p1_starter.py’s time_best: warmup once, disable GC for the timed region (and restore it), repeat at least 5 times, return the minimum. Time only the operation under test — build every input outside the timed call.
3. Measurement across growing n. Run each program at a schedule of doubling sizes. A, B, and C can go large (e.g. 1,000 → 256,000). D is O(n²) — keep it small (e.g. 500 → 8,000) or you’ll wait all night. Record program, n, and best-milliseconds to data.csv.
4. A plot. Plot time vs n for the four programs. A log-log plot is ideal (straight lines whose slope is the exponent), but a clear linear plot or even a clean hand-drawn graph is acceptable if labeled. Save as plot.png or document the equivalent.
5. Confirmation in writing. In REPORT.docx, for each program, state the ratio between consecutive rows (how much the time grew when n doubled) and confirm or correct your prediction. If a measurement surprised you, say so and reason about why.

Example output (your measure.py should print something like)

program           n      best_ms
A_middle       1000       0.0001
A_middle       2000       0.0001
A_middle       4000       0.0001
...
D_pairs         500       2.5186
D_pairs        1000      10.2010
D_pairs        2000      40.8989
D_pairs        4000     166.2673

(Notice D’s time roughly quadrupling per doubling — that’s O(n²) confirmed.)

Normal-tier rubric (out of 100)

Medium Tier (+up to 25% extra credit)

M1. Measure space, too

Add memory measurement. For at least two of the programs (or two strategies that compute the same answer), use tracemalloc to report the bytes allocated, and sys.getsizeof where a single object’s shallow size is the honest number. Add a short section to REPORT.docx reporting the space cost alongside the time cost.

M2. Opposite directions

Show one concrete case where the time cost and the space cost point in opposite directions — where buying speed costs memory, or saving memory costs speed. The list-vs-generator example from §1.5 is one such case; a precomputed lookup table vs recomputing on demand is another. Measure both axes, present them side by side, and write the tradeoff in two or three sentences: under what constraint would you pick each? This naming-of-the-constraint is the architect’s move; don’t skip the sentence where you commit to one.

Hard Tier (+up to 25% additional extra credit)

H1. Catch the asymptotics lying

Somewhere in the subjects — or in a variant you construct — find a case where the measured behavior contradicts the apparent Big-O. Two reliable sources (you choose at least one and demonstrate it with numbers):

• A constant factor or crossover. Two algorithms with different Big-O where the asymptotically worse one is faster at every n you’d realistically run, because its constant factor is smaller. Find or build the pair, measure across n, and locate (or bound) the crossover point where the better Big-O finally wins.
• A cache / memory-layout effect. A program whose measured cost is dominated by how its data sits in memory, not by its operation count. (For example: summing a Python list vs summing the same values when scattered across many small objects, or appending to the end of a list — amortized O(1) — vs insert(0, x) at the front, which the single loop makes look linear but is secretly O(n²). Show the front-insertion curve quadrupling per doubling and explain it.)

Measure it. Plot it. Then write the analysis: state the apparent Big-O, state the measured behavior, and explain precisely what cost the asymptotic analysis ignored that the machine charged you for. This is the most important paragraph you will write all week. It is the first appearance of the theme that runs through the whole book — Big-O is a tool, not a god — and the architect’s whole edge is knowing when to trust it and when to reach for the clock.

H2. Predict the ministry’s future

Return to the setup. Using your measured curves, extrapolate: at 50,000 records, estimate the runtime of each of the four operation-shapes. Which stay comfortably fast? Which become a problem? Write a short recommendation to the ministry — in plain English a non-engineer could act on — naming which shapes of operation must be redesigned before the merge and which are fine as-is. Cite your own numbers. This is a measured, justified architecture recommendation: exactly what you were hired to produce.

Submission

Submit one URL: a public GitHub repository (see Appendix A for setup).

What the repo must contain

1. measure.py — your finished harness and experiment runner (the four subject programs unchanged).
2. data.csv — the numbers your experiment produced.
3. plot.png — the curves (or a clearly documented equivalent).
4. REPORT.docx — the one-page report, in this shape:

# Project 1 — Measure, Predict, Confirm

**Tier targeted:**  Normal / Medium / Hard
**Machine:**  (CPU, RAM, OS, Python version — measurements depend on hardware)

## Predictions (written BEFORE measuring)
- Program A: O(__) — time should ____ as n doubles, because ____.
- Program B: ...
- Program C: ...
- Program D: ...

## Results
(your table + plot, with the ratio between consecutive rows for each program)

## Confirmation
(for each program: did the curve match the prediction? what was the doubling ratio?
 where were you surprised, and why?)

## Space  (Medium)
## Opposite directions  (Medium)
## Where the asymptotics lied  (Hard)
## Recommendation to the ministry at 50,000 records  (Hard H2)

**AI usage:**  NONE — Phase 1.  Signed: <your name>

5. README.txt — how to run measure.py, what it produces, and the AI honesty line.

Hints (Read Before You Begin)

• Write the predictions first and don’t go back and edit them. The value of this project is the honest gap between what you guessed and what the machine did. If you measure first and then “predict,” you’ve learned nothing and the grader will see it.
• Build inputs outside the timed call. The number-one timing bug (you made it on purpose in Rep 5). The clock starts immediately before the operation and stops immediately after — nothing else lives in between.
• Take the minimum, not the mean. The OS only ever slows a run down. The fastest run is the cleanest measurement of your code.
• Keep D small. O(n²) at n = 100,000 is billions of operations. Cap D’s sizes where each run finishes in a second or two, and let the ratio (quadrupling per doubling) carry the proof — you don’t need huge n to see the shape.
• Plot log-log if you can. On log-log axes, each complexity class is a straight line whose slope is its exponent: O(1) is flat, O(n) has slope 1, O(n²) has slope 2. The slopes make the classes visible at a glance.
• Your numbers won’t match the book’s, and shouldn’t. Different hardware shifts the magnitudes. What must match is the ratio — how the time responds to doubling n. Compare ratios, not milliseconds.

What Mastery Looks Like (Beyond the Rubric)

A great Project 1 is not a great pile of code — it’s barely a hundred lines. A great Project 1 is a great report. The predictions are committed and specific. The harness is honest enough that you’d stake a production decision on its numbers. And the confirmation section reads like an architect thinking out loud: “I predicted C would beat B at large n because n log n grows slower than… wait, no — C is the sort, it’s slower than the linear sum; let me re-read. Corrected.”

A great Project 1 treats a surprise as a gift. When the measurement disagrees with the prediction, the great submission doesn’t quietly fix the prediction — it keeps the wrong prediction visible and explains what it missed. That intellectual honesty is the whole discipline. The ministry doesn’t need an engineer who’s always right. It needs one who notices fast when they’re wrong, and says so, with numbers.

And a great Hard tier has the paragraph that makes the rest of the book possible: the one where you watched the asymptotically-worse code win, or watched a single loop behave like a nested one, and you explained exactly which cost Big-O hid from you. Once you’ve written that paragraph honestly, you will never again recite a complexity class as though it were the last word. You’ll reach for the clock. That reflex is the architect’s, and you’ll have earned it in Week 1.

Coach’s Note — Students rush this project because it “has no real code.” Those students turn in a prediction-free pile of timings and a one-line “yeah it matched.” It did not teach them anything, because the learning was never in the timings — it was in committing to a prediction and being held to it by a clock you built yourself. Slow down. Write the prediction. Build the honest harness. Let the machine grade your guess. That loop, repeated for sixteen weeks at growing scale, is how a coder becomes an architect.

When You’re Done

1. Run measure.py. Confirm it prints a clean table and writes data.csv.
2. Open your plot. Can you see the four shapes? Is the quadratic one obviously bending upward?
3. Re-read your predictions. Did you keep the wrong ones visible and explain them, or did you quietly “fix” them? Fix that, not the predictions.
4. Read REPORT.docx aloud. Could the nervous volunteer — who is not an engineer — act on your recommendation? If not, rewrite for him.
5. Push to GitHub. Submit the URL.
6. Read Chapter 2. Arrays next — the memory you can feel — and your first hand-built structure, the dynamic array, whose amortized-O(1) append you’ll prove with the very harness you built this week.

A theological footnote. Jesus’ tower-builder is not condemned for building. He is condemned for building without counting — for the haste that mistakes enthusiasm for readiness and leaves a half-finished monument to its own folly. The counting is not the opposite of building; it is the first faithful act of it. When you sat down this week and counted the cost of four small programs before recommending what the ministry should keep, you practiced — in the smallest possible key — the wisdom the verse commends. The architect counts first. So does the disciple.

See you next week.