Chapter 2 — Reps

Conditioning, not grading. Python reps this week, all about arrays, memory, and the doubling trick.

Ground rules:

1. Type every line yourself. No copy-paste. The fingers learn what the eyes skim past.
2. Run everything. Predict the output first, in writing, then run and compare. The gap between your prediction and reality is the lesson.
3. AI stays OFF. Phase 1. You cannot reason about the cost of a structure you have never built with your own hands. Build it.
4. Measure honestly. When a rep says “time it,” use time.perf_counter() and run each measurement a few times — the first run is often slow (warm-up). Report the median, not the best.

These reps assume Python 3.10+ on your own machine (Appendix A). The chapter’s code/ folder has runnable demos referenced below.

Reps 1–3: Feeling the Cost Table

Rep 1 — append vs insert(0, x)

Write two functions. Each builds a list of n integers, but one uses append and the other uses insert(0, x):

def build_with_append(n):
    data = []
    for i in range(n):
        data.append(i)
    return data

def build_with_front_insert(n):
    data = []
    for i in range(n):
        data.insert(0, i)        # always at the front
    return data

First, predict in writing: which is faster, and by what shape (a constant factor? a different Big-O)? Then time both at n = 1000, 5000, 25000. Confirm the front-insert version grows quadratically (each insert(0,...) is O(n), done n times = O(n²)), while append grows linearly. Write one sentence relating your measured numbers to §2.6.

Rep 2 — pop() vs pop(0)

Take a list of 100,000 integers. Time draining it two ways:

def drain_from_end(data):
    while data:
        data.pop()       # O(1) — removes the last element

def drain_from_front(data):
    while data:
        data.pop(0)      # O(n) — shifts everything left each time

Make a fresh copy for each (draining mutates). Predict, then measure. Explain in one sentence why pop(0) is the quadratic trap from the Common Bugs section.

Rep 3 — The cost table, from memory

Close the book. On paper, reproduce the array cost table from §2.6 — index, append, pop-from-end, insert at i, delete at i, search unsorted, search sorted — with the cost and a one-clause reason for each. Then open the book and check. Any cell you got wrong, write three times. This table is the first row of your master cost table; you will carry it all term.

Reps 4–6: Watching Python’s List Grow

Rep 4 — Find the resize points

Python’s list over-allocates. You can watch it happen:

import sys

data = []
last = -1
for i in range(130):
    size = sys.getsizeof(data)
    if size != last:
        print(f"length {len(data):3d}  ->  {size} bytes  (RESIZE)")
        last = size
    data.append(i)

Run it. You’ll see the byte-size jump only at certain lengths — those are the resizes. Write down the lengths at which resizes happen (0, 4, 8, 16, 25, …). Notice the gaps grow but not by a clean doubling — that’s CPython’s ~1.125x over-allocation from §2.5. Confirm: between resizes, append did not change the buffer size, so those appends were the free O(1) case.

Rep 5 — getsizeof lies (the boxing rep)

Run this and explain the result:

import sys

small = [1, 2, 3]
big   = [10**100, 10**100, 10**100]    # three huge integers

print("small list getsizeof:", sys.getsizeof(small))
print("big   list getsizeof:", sys.getsizeof(big))
print("a small int:", sys.getsizeof(1))
print("a huge  int:", sys.getsizeof(10**100))

The two lists report nearly the same getsizeof, even though one holds tiny ints and one holds enormous ones. Explain why in two sentences, using §2.5: the list stores pointers (same size either way); the integer objects they point at are stored separately and are not counted by getsizeof(list). Then write a function deep_size(lst) that returns getsizeof(lst) + sum(getsizeof(x) for x in lst) and show the two lists now differ enormously.

Rep 6 — Python list vs the idea of a C array

You can’t write C++ here, but you can reason about it. A C++ vector<int> holding one million ints uses about 4 * 1,000,000 = 4 MB. Estimate the cost of the same million small ints in a Python list:

import sys
data = list(range(1_000_000))
list_overhead = sys.getsizeof(data)                 # the pointer array + header
int_cost      = sum(sys.getsizeof(x) for x in data) # the boxed integers
print("list pointer array:", list_overhead, "bytes")
print("boxed integers:    ", int_cost, "bytes")
print("python total:      ", list_overhead + int_cost, "bytes")
print("c++ vector<int>:    ~4,000,000 bytes")

Report the ratio of Python’s total to C++‘s ~4 MB. Write one sentence on why the gap exists (boxing + pointer indirection) and one sentence on when you’d accept the gap anyway (flexibility, developer time) and when you wouldn’t (raw numeric throughput → NumPy).

Reps 7–9: Building the Doubling Logic By Hand

Rep 7 — Resize and copy, by hand

No DynamicArray class yet — just the core move. Given a “full” fixed buffer, grow it:

def grow_double(buffer, length):
    """Return a new buffer with double the capacity, with the `length`
    existing elements copied in. Do NOT use list slicing or list.copy()
    or list comprehension over the old buffer — copy one element at a time
    in an explicit loop, the way the hardware does it."""
    old_capacity = len(buffer)
    new_capacity = old_capacity * 2 if old_capacity > 0 else 1
    new_buffer = [None] * new_capacity
    for i in range(length):
        new_buffer[i] = buffer[i]
    return new_buffer

Test it: start with buffer = [10, 20], length = 2. Grow it. Confirm the new buffer has capacity 4, the first two slots are 10, 20, and the rest are None. Then grow that and confirm capacity 8. You just wrote the expensive O(n) step of append — count the copies each grow makes.

Rep 8 — Count the total copies to build n elements

Instrument the doubling to count every element-copy made while building up n elements from empty:

def total_copies_to_build(n):
    capacity = 0
    length = 0
    copies = 0
    for _ in range(n):
        if length == capacity:                 # full — must grow
            new_capacity = capacity * 2 if capacity > 0 else 1
            copies += length                   # copy all existing elements
            capacity = new_capacity
        length += 1                            # then write the new element
    return copies

Run it for n = 1, 2, 4, 8, 1000, 1_000_000. Predict first: the chapter says total copies ≈ n (specifically a bit under 2n worst case, and for exact powers of two it’s n - 1). Confirm total_copies_to_build(1_000_000) is on the order of a million, not a trillion. This is the amortized-O(1) proof from §2.4, in numbers you generated.

Rep 9 — Amortized vs worst-case, in one timing

Build a list of 2,000,000 elements with append, but time each individual append and record the slowest one and the average:

import time

data = []
slowest = 0.0
total = 0.0
N = 2_000_000
for i in range(N):
    t0 = time.perf_counter()
    data.append(i)
    dt = time.perf_counter() - t0
    total += dt
    slowest = max(slowest, dt)

print(f"average append: {total / N * 1e9:.1f} ns")
print(f"slowest append: {slowest * 1e9:.1f} ns")

The slowest append (a resize copying ~2M elements) will be hundreds or thousands of times the average. Write one sentence: this is exactly why append is amortized O(1) and not worst-case O(1) — most are tiny, a rare few spike, the average stays constant.

Reps 10–11: Cache Locality You Can Time

Rep 10 — A starter DynamicArray skeleton

Type out this skeleton (you’ll finish it in the project — for now just get the shape and the invariant in your fingers):

class DynamicArray:
    def __init__(self):
        self._capacity = 1
        self._length = 0
        self._buffer = [None] * self._capacity   # raw storage; NOT used as a Python list

    def __len__(self):
        return self._length

    def get(self, i):
        if not 0 <= i < self._length:
            raise IndexError(f"index {i} out of range for length {self._length}")
        return self._buffer[i]

    def append(self, value):
        if self._length == self._capacity:       # invariant: length <= capacity, always
            self._resize(self._capacity * 2)
        self._buffer[self._length] = value
        self._length += 1

    def _resize(self, new_capacity):
        new_buffer = [None] * new_capacity
        for i in range(self._length):             # explicit copy — the O(n) step
            new_buffer[i] = self._buffer[i]
        self._buffer = new_buffer
        self._capacity = new_capacity

Append 20 elements and after each, print len, _capacity, and the _buffer. Watch capacity go 1, 2, 4, 8, 16, 32 and watch the None padding appear after each resize. Seeing the padding is seeing the over-allocation that makes appends free.

Rep 11 — Sequential vs scrambled traversal

Feel the cache. Run code/cache_locality.py (or write your own):

import time, random

N = 5_000_000
data = list(range(N))
order = list(range(N))
random.shuffle(order)

def timed(fn, *args):
    t0 = time.perf_counter()
    fn(*args)
    return time.perf_counter() - t0

def sum_sequential(data):
    total = 0
    for i in range(len(data)):
        total += data[i]
    return total

def sum_scrambled(data, order):
    total = 0
    for i in order:
        total += data[i]
    return total

print("sequential:", timed(sum_sequential, data))
print("scrambled: ", timed(sum_scrambled, data, order))

Both are O(n) and touch every element exactly once. Predict which is faster and why before running. The scrambled version is typically noticeably slower (CPython’s interpreter overhead masks some of it, but the cache effect is real). Write two sentences relating the gap to §2.2: sequential access wins the cache-line bet on most reads; scrambled access loses it on most reads. This is the constant factor that Big-O cannot see — and the reason the array’s contiguity is a gift.

Done? One Last Thing.

From scratch, no looking — write a function is_amortized_constant(n) that returns the total element-copies performed while appending n items to a doubling dynamic array (capacity starts at 1, doubles when full), and assert that the result is always strictly less than 2 * n:

def is_amortized_constant(n):
    # build the doubling array's copy count by hand
    # return total copies; it must be < 2 * n for all n >= 1
    ...

for n in [1, 2, 3, 7, 8, 100, 1000, 1_000_000]:
    copies = is_amortized_constant(n)
    assert copies < 2 * n, f"FAIL at n={n}: {copies} copies"
    print(f"n={n:>9}  copies={copies:>9}  ratio={copies/n:.3f}")

If every assertion passes and the ratio hovers below 2, you have proven — with your own code, no AI — that doubling growth gives amortized O(1) append. If you can write this cold, you have the move, and the project’s hardest claim is already in your hands.

Up next: Project 2 — Project 2: Build a Dynamic Array.