A First Taste of Algorithms · Lab 6: Counted and Clocked

5. The first plot

Six chapters of tables; time for the picture. matplotlib draws it — three moves for now: plt.plot draws a curve from lists of x and y values, plt.loglog does the same with both axes multiplying (so power laws become straight lines), and plt.show() reveals.

import matplotlib.pyplot as plt

ns = [8, 32, 128, 512, 2048]
ins_counts = []
mrg_counts = []
for n in ns:
    worst = list(range(n, 0, -1))
    ins_counts.append(insertion_sort_count(worst)[1])
    mrg_counts.append(merge_sort_count(worst)[1])

plt.loglog(ns, ins_counts, "o-", label="insertion (counted)")
plt.loglog(ns, mrg_counts, "s-", label="merge (counted)")
plt.xlabel("n")
plt.ylabel("steps")
plt.legend()
plt.show()

Two nearly straight lines, diverging — and their slopes are the exponents: the insertion line climbs twice as steeply (n² against n·log n’s almost-1). You are looking at Θ notation before it had a name: the plot ignores constants (they only shift a line up or down on these axes) and shows shape, which is exactly the deal the notation offers. Then plot the clocked data from §4 the same way and find the crossover as a crossing of curves — the picture of the constants’ neighborhood.

6. The humbling

One more clock. Python ships with sorted() — Timsort, the deep water’s engineered descendant of exactly the two algorithms on your screen. Predict the ratio before running: your merge sort versus the professionals, n = 2,048, shuffled. Twice as fast? Five times?

items = list(range(2048))
random.shuffle(items)
t_mine = clock(merge_sort, items, 11)
t_builtin = clock(sorted, items, 11)
print("mine:", round(t_mine * 1e3, 2), "ms   built-in:",
      round(t_builtin * 1e3, 2), "ms   ratio:", round(t_mine / t_builtin))

The ratio is humbling — and the humility has structure, so spend it wisely. The built-in is the same Θ(n log n) as yours; the fence guarantees it cannot be a different shape. The entire margin is constants: decades of engineering, plus the quiet fact that sorted runs in C beneath Python’s floor. Your algorithm and theirs will scale identically — double n and both double-and-a-bit — which you can verify by clocking both at 4,096 and checking the two ratios-to-before. The shapes are yours; the constants are an industry; and you now own the instrument that tells those two stories apart.

Break it

Predict first. Run second. Explain any gap third.

1. Feed §2’s counted race already-sorted inputs instead of reversed: list(range(n)) in both places. Predict both columns before running. One algorithm’s column collapses to almost nothing; which, why, and what is its exact new count? Connect to the chapter’s recorded virtue — and to why “insertion sort is Θ(n²)” needed the words worst case attached.

2. Sabotage the timing protocol: change clock so all repeats share one list instead of sorting fresh copies (copy = items instead of list(items)). Predict what happens to insertion sort’s clocked numbers and why — then run §4’s race with the corrupted clock and watch the standings change. Which algorithm benefited from the corruption, and what does Break-it 1 have to do with it? (Measurement bugs that flatter one contestant are the most dangerous kind; you have just built one.)

3. Time a single run instead of a median of 51 (set repeats to 1) and run the n = 64 comparison ten times in a loop, printing the winner each time. Predict: same winner all ten times? Report the tally. The median protocol exists because of what you just witnessed; state the lesson in one sentence about believing any single measurement, anywhere, ever.

4. Build the chapter’s counting sort for exam scores (whole numbers 0–100): 101 buckets, one pass in, read out in order. Count its touches at n = 1,000,000 (simulate with random scores) and clock it against sorted on the same data. Predict the winner first — you are betting a linear algorithm against the best-engineered n log n on Earth. Then betray it: change the keys from scores to random.random() decimals and explain, in the theorem-and-gate language of the chapter, why your algorithm doesn’t just slow down but stops making sense.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses