Interactive Companions

One slider drives all seven growth curves (p. 504) and the classification table (p. 505) at once — watch operation counts turn into actual wall-clock time.

Step through the whitelist filter's search loop compare by compare (and watch == fail), measure ~N/2 compares per hit and N per miss, then run the doubling test: ratio 4, quadratic.

Move lo and hi over the sorted whitelist and watch the half-open interval, mid and both halves update; predict-the-mid quiz and the (lo + hi)/2 overflow.

Step through the recursive search() line by line with its call stack, for hits and misses — then shuffle the array and watch binary search miss keys that are there.

Build the tree of middles level by level for N = 2^k − 1: every miss is a top-to-bottom path of lg(N+1) compares.

Pick a number, ask up to 8 yes/no questions, watch its binary digits reveal themselves one at a time.

The exact same questions, acted out physically with a two-pan scale and 64/32/16/8/4/2/1-unit weights.

Generalize from integers to real numbers: solve Φ(x) = y for any monotone curve, no closed-form inverse required.

Sort the 16 names from the slides one compare at a time, watch the trace build row by row (p. 544), and compare the cost of sorted, random and reversed input: ~N, ~N²/4, ~N²/2.

Merge two sorted halves one move at a time (equal keys keep their order), step through the whole recursion with its call stack and trace (p. 551), count 2N data moves on each of the lg N levels, and compare predicted times with insertion sort.

Sort the words, count the runs, sort the counts: rank × count stays roughly constant in four novels. Fit the slope on a log-log plot, predict counts from 1/k, and try your own text.

Watch the call stack of a recursion fill up and overflow, run the same input on a stack and a queue, look inside ArrayStackOfStrings (n++, --n, loitering, a capacity crash), and test which pop orders a stack can make.

Build a linked list one assignment at a time, run LinkedStackOfStrings and the resizing array on tobe.txt, evaluate expressions with two stacks or in postfix, and trace a FIFO queue made of linked nodes.