Chapter 1 — Reps
Conditioning, not grading. First Python reps this week, plus the timing harness you’ll reuse all of Phase 1.
Ground rules:
- Type every line yourself. No copy-paste — not even from the chapter’s
code/files. The harness has to live in your fingers, not your clipboard. - Run everything. Every snippet, every timing, every prediction. A rep you didn’t run is a rep you didn’t do.
- AI is OFF. Phase 1, all eight weeks. You cannot reason about a cost you’ve never paid. Build it yourself.
- Predict before you measure. Every timing rep starts with a written guess. Then you confirm or correct it. The gap between guess and measurement is where the learning is.
You need a working Python 3 on your own machine — see Appendix A. Everything here runs with a bare python3 file.py.
Reps 1–3: First Python
Rep 1 — Hello, Python
You wrote this in Java a hundred times. Write it in Python and feel the differences.
hello.py:
def greet(name):
return "Hello, " + name + "."
def main():
for who in ["Maya", "Marcus", "stranger"]:
print(greet(who))
if __name__ == "__main__":
main()Run it: python3 hello.py. Now notice, out loud, the differences from Java: no class required, no public static void, no type on name, no ;, the block is defined by indentation and a colon, and the entry point is a if __name__ == "__main__": guard instead of a main the runtime finds automatically. Write a one-sentence note on each difference in a comment at the bottom of the file.
Rep 2 — Dynamic Typing, On Purpose
Type this and run it. Predict what each print shows before you run it.
x = 5
print(type(x), x)
x = "five"
print(type(x), x)
x = [5, "five", 5.0]
print(type(x), x)The name x was rebound to a completely different kind of object three times, and Python never complained. In Java this would not compile. Write a comment: in one sentence, what does dynamic typing buy you, and in one sentence, what does it cost you (hint: which Coding 2 muscle now has to do the compiler’s old job)?
Rep 3 — Read the Big-O Off the Code
For each snippet, write the Big-O in a comment — from the code alone, without running it. Then write one sentence justifying it.
# (a)
def a(data):
return data[-1]
# (b)
def b(data):
for x in data:
if x == 0:
return True
return False
# (c)
def c(data):
for x in data:
for y in data:
if x + y == 0:
return True
return False
# (d)
def d(sorted_data, target):
lo, hi = 0, len(sorted_data) - 1
while lo <= hi:
mid = (lo + hi) // 2
if sorted_data[mid] == target: return mid
if sorted_data[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
# (e)
def e(data):
return sorted(data)Answers to check yourself against: (a) O(1), (b) O(n) — worst case scans all, (c) O(n²) — nested loops over the same data, (d) O(log n) — halving window, (e) O(n log n) — that’s what sorted costs. If you missed one, re-read §1.2.
Reps 4–6: The Timing Harness
Rep 4 — Your First Measurement
Type this and run it. It is the smallest honest timing you can write.
import time
def total(data):
s = 0
for x in data:
s += x
return s
data = list(range(1_000_000))
start = time.perf_counter()
result = total(data)
elapsed = time.perf_counter() - start
print(f"sum = {result}, time = {elapsed * 1000:.3f} ms")Run it three times. Notice the time varies between runs — that variation is the noise §1.4 warned you about. Write down the three numbers and the spread between them. That spread is why the next two reps exist.
Rep 5 — Time the Wrong Thing (a deliberate mistake)
Modify Rep 4 so the data is built inside the timed region:
start = time.perf_counter()
data = list(range(1_000_000)) # building the input is now being timed!
result = total(data)
elapsed = time.perf_counter() - startRun it. Your time roughly doubles (or more). You just measured the construction of the input plus the algorithm, not the algorithm. Write a comment: which line should be outside the timed region, and why. This is the single most common timing bug; make it once, on purpose, so you never make it by accident.
Rep 6 — Build the Harness
Build the real harness from scratch — no peeking at code/timing_harness.py until you’re done. It must do all four defenses from §1.4.
import gc
import time
def time_call(func, *args, repeats=5):
func(*args) # 1. warmup
gc_was_on = gc.isenabled()
gc.disable() # 3. GC off
best = float("inf")
try:
for _ in range(repeats): # 2. repeat, take the minimum
start = time.perf_counter()
func(*args)
best = min(best, time.perf_counter() - start)
finally:
if gc_was_on:
gc.enable()
return best # 4. return the minimumThen time a linear program across doubling n:
def total(data):
s = 0
for x in data:
s += x
return s
for n in [100_000, 200_000, 400_000, 800_000]:
data = list(range(n)) # built OUTSIDE the timed call
ms = time_call(total, data) * 1000
print(f"n={n:>8} {ms:>8.3f} ms")Confirm the time roughly doubles each time n doubles. That doubling is O(n), measured. Write the four numbers and the ratio between consecutive rows in a comment.
Reps 7–9: Confirming the Curves
Rep 7 — Confirm O(1)
Using your harness from Rep 6, time a constant-cost program across the same doubling sizes:
def middle(data):
return data[len(data) // 2]Predict first (write it down): what should the time do as n grows? Now measure. The time should stay roughly flat — it does not grow with n, because indexing is one operation regardless of size. If you see it climb, you’re probably timing the list(range(n)) construction; check that it’s outside the call.
Rep 8 — Confirm O(log n)
Time binary search on a sorted list as n doubles. Use sizes from 1,000 up to 1,000,000 (logarithmic curves are so flat you need a huge range to see them move).
def binary_search(sorted_data, target):
lo, hi = 0, len(sorted_data) - 1
while lo <= hi:
mid = (lo + hi) // 2
if sorted_data[mid] == target: return mid
if sorted_data[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
for n in [1_000, 10_000, 100_000, 1_000_000]:
data = list(range(n))
ms = time_call(binary_search, data, n - 1) * 1000 # search for last
print(f"n={n:>9} {ms:>8.4f} ms")A thousand-fold increase in n should add only a tiny, near-constant amount of time. Write a comment: by roughly how many steps did the work grow when n went from 1,000 to 1,000,000? (Hint: log₂(1000) ≈ 10, log₂(1,000,000) ≈ 20. The work barely doubled while n grew a thousand-fold. That is the power of logarithmic.)
Rep 9 — Confirm O(n²)
Time the naive duplicate check on all-unique input (worst case — it never returns early). Keep n small.
def has_duplicate(data):
n = len(data)
for i in range(n):
for j in range(i + 1, n):
if data[i] == data[j]:
return True
return False
for n in [500, 1_000, 2_000, 4_000]:
data = list(range(n)) # all unique -> full scan
ms = time_call(has_duplicate, data) * 1000
print(f"n={n:>6} {ms:>9.3f} ms")Predict first, then measure. Each doubling of n should roughly quadruple the time. Write the four numbers and the ratio between consecutive rows in a comment. If the ratio is about 4, you’ve confirmed O(n²) with your own hands. Now imagine this curve at n = 1,000,000 and reread the cost table in §1.3.
Reps 10–11: Space and the Lie
Rep 10 — Measure Space Two Ways
Type and run:
import sys
import tracemalloc
# Shallow: sys.getsizeof on single objects
print("empty list:", sys.getsizeof([]))
print("list of 1000:", sys.getsizeof(list(range(1000))))
print("int 0:", sys.getsizeof(0))
print("int 10**100:", sys.getsizeof(10 ** 100))
# Deep: tracemalloc on a block
tracemalloc.start()
before = tracemalloc.get_traced_memory()[0]
big = [i * i for i in range(100_000)]
after = tracemalloc.get_traced_memory()[0]
tracemalloc.stop()
print("list of 100k squares:", after - before, "bytes")Then replace the list comprehension [i * i for i in range(100_000)] with a generator (i * i for i in range(100_000)) and re-run the tracemalloc block. Write a comment: how many bytes did each cost, and why is the generator so much cheaper? (Reread §1.5.) Which would you choose if you needed to walk the squares once and never again? Which if you needed random access to any square at any time?
Rep 11 — Find the Lie
Here are two functions that both build a list of n items by repeated insertion. One appends to the end; one inserts at the front. Both look O(n) — a single loop. Predict whether they cost the same. Then measure.
def build_back(n):
out = []
for i in range(n):
out.append(i) # add to the end
return out
def build_front(n):
out = []
for i in range(n):
out.insert(0, i) # add to the FRONT
return out
for n in [2_000, 4_000, 8_000, 16_000]:
back = time_call(build_back, n) * 1000
front = time_call(build_front, n) * 1000
print(f"n={n:>6} back={back:>8.3f} ms front={front:>9.3f} ms")build_back is genuinely O(n) and roughly doubles per doubling. build_front is secretly O(n²): every insert(0, i) shifts every existing element one slot to the right, so the inner cost grows with the list. Confirm that front quadruples per doubling while back only doubles. Write a comment explaining, in C++/Java memory terms, why inserting at the front of a contiguous array costs O(n) (§1.7’s “keep your C++ eyes open”). This is your first hands-on proof that Python hides the cost — and that your old memory model is the X-ray that reveals it.
Done? One Last Thing.
Cold, no looking back — this is the P1 move in miniature.
Write a fresh file. In it:
- Write a function
f(data)that returnssum(x for x in data if x % 2 == 0)— the sum of the even numbers. - Predict, in a written comment, the Big-O of
fand what its timing should do asndoubles. Commit to a number before you measure. - Paste in your harness from Rep 6.
- Time
facrossn = [100_000, 200_000, 400_000, 800_000], with inputs built outside the timed call. - Confirm or correct your prediction in a final written comment: did the curve match? What’s the ratio between consecutive rows? If it didn’t match, what did your prediction miss?
If you can do that whole loop — predict, instrument, measure honestly, confirm in writing — without looking anything up, you have the architect’s core move. That is Project 1, scaled down to one function.
Up next: Project 1 — Project 1: Measure, Predict, Confirm.