The Benchmark That Measured the Harness, Not the Algorithm
Ms. Delgado's Advanced Computer Science class runs a benchmark comparing linear and binary search in Python. Each student searches a sorted list of 1,000 integers and a sorted list of 1,000,000 integers for 100 target values, timing the whole loop with time.time(). Targets come from random.randint(1, 60), and the lists contain the integers 1 through n in ascending order, so every target is found within the first 60 positions. The recursive search takes a list and a target: if the list is empty it returns False; otherwise it computes mid = len(a)//2, returns True when a[mid] equals the target, and otherwise recurses on a[:mid] or on a[mid+1:]. Median results over five runs are: linear on 1,000 items, 0.5 ms; binary on 1,000 items, 1.1 ms; linear on 1,000,000 items, 240 ms; binary on 1,000,000 items, 205 ms. Four of seven groups conclude that binary search is not meaningfully faster, and two groups write that Big-O notation is unreliable for real programs. The unit performance task is in two days.
1. Identify the specific flaws in the experiment and in the implementation, and explain how each flaw would change the measured numbers.
Read the worked answer
Two independent flaws, and either one alone would produce the reported pattern. First, the input distribution. Targets are drawn from 1 to 60 while the list holds 1 through n in ascending order, so linear search always terminates within its first 60 comparisons. Linear search is being measured in its best case at both sizes, which is why the 1,000,000-item time (240 ms) is nowhere near 1,000 times the 1,000-item time. The n-dependence has been engineered out of the experiment. Second, a[:mid] builds a brand-new list at every level of the recursion. The copied elements total n + n/2 + n/4 + ... which is less than 2n, so each call is Theta(n) in time and memory even though it performs only Theta(log n) comparisons. Once slicing dominates, doubling the input roughly doubles the time, which is exactly the modest 1.1 ms to 205 ms change across a thousandfold increase in n. A correct binary search should differ by roughly a factor of two, since log2(1,000) is about 10 and log2(1,000,000) is about 20. Neither number supports a claim about Big-O; both measure the harness.
2. Rewrite the search so that timing reflects the comparison count, and describe the other changes needed for the comparison across input sizes to be fair.
Read the worked answer
Keep two indices instead of copying: set lo to 0 and hi to len(a) - 1, loop while lo is at most hi, compute mid = (lo + hi) // 2, compare, then move hi to mid - 1 or lo to mid + 1. Space becomes constant and the running time becomes Theta(log n) comparisons. For fairness: draw targets uniformly across the whole domain and include values that are absent, because a miss costs the full log n while a hit averages about one comparison less; run enough searches that total elapsed time exceeds timer resolution, since 100 searches at roughly a microsecond each is far too few; time with time.perf_counter() and subtract loop overhead by timing an empty loop; warm up once so import and caching effects stay out of the first measurement; and report per-search averages. The strongest evidence is to instrument a comparison counter in both functions. At n = 1,000,000 a correct binary search makes at most 20 comparisons against up to 1,000,000 for linear search, and the counter makes the asymptotic claim visible without depending on the clock at all.
3. How should Ms. Delgado respond to and grade the groups whose conclusions were wrong, including the claim that Big-O is unreliable?
Read the worked answer
Treat the wrong conclusion as a defensible but unfinished inference and grade the evidence rather than only the verdict. The rubric needs a strand for experimental design (were confounds identified?), a strand for algorithmic analysis (can the student explain why slicing changes the complexity class?), and a strand for revision. The groups who wrote that Big-O is unreliable have made a category error worth surfacing publicly: Big-O describes the growth of a model, while a stopwatch measures that model plus constants, library behavior, and timer limits. A whole-class debrief using the corrected code and the comparison-counter data lets those groups repair their reasoning rather than merely lose points. Practically: return the reports ungraded, give one class period to rerun with the fixed search and full-range targets, require a two-paragraph revision naming one confound and one implementation effect, then grade the revision. This preserves accountability while making the assessment measure whether students can fix reasoning. Grading the original analysis strand as unsatisfactory is defensible; giving credit that a lucky correct guess would have earned is not.