A Theoretician’s Guide to the Experimental Analysis of Algorithms
📜 Abstract
This paper presents an informal discussion of issues that arise when one attempts to analyze algorithms experimentally. It is based on lessons learned by the author over the course of more than a decade of experimentation, survey paper writing, refereeing, and lively discussions with other experimentalists. Although written from the perspective of a theoretical computer scientist, it is intended to be of use to researchers from all fields who want to study algorithms experimentally. It has two goals: first, to provide a useful guide to new experimentalists about how such work can best be performed and written up, and second, to challenge current researchers to think about whether their own work might be improved from a scientific point of view. With the latter purpose in mind, the author hopes that at least a few of his recommendations will be considered controversial.
✨ Summary
Overview
David S. Johnson presents a methodological guide to experimental analysis of algorithms, arguing that worst-case and average-case theory cannot by themselves characterize real-world performance. The paper distinguishes four motivations for implementing algorithms: applying them to a practical problem, comparing competing methods in a “horse race,” understanding algorithmic behavior, and generating conjectures about average-case performance.
The central framework consists of ten principles: perform newsworthy experiments; connect the study to prior literature; use testbeds that support general conclusions; design experiments efficiently; use reasonably efficient implementations; ensure reproducibility; ensure comparability; report the full story; draw justified conclusions and seek explanations; and present data informatively. Johnson develops these principles through concrete recommendations, including exploratory experimentation, variance reduction, bootstrapping, self-documenting programs, benchmark-based machine calibration, profiling, normalized running-time plots, and preservation of code, data, instances, and parameter settings.
The paper repeatedly warns against narrow or misleading evaluations. Examples include relying on unstructured random instances, using already-solved testbeds, comparing results measured on uncalibrated machines, hand-tuning parameters without documenting the process, using running time as an ill-defined stopping rule, reporting only the best result from randomized runs, hiding anomalies, extrapolating asymptotic behavior from small instances, and presenting tables or figures that obscure rather than clarify trends. A recurring theme is that experimental results should support conclusions that are scientifically meaningful beyond the exact implementation, machine, and instances used.
Influence and subsequent use
The paper became part of the methodological literature surrounding experimental algorithmics and algorithm engineering. The American Mathematical Society published it as a chapter in the 2002 DIMACS volume on implementation challenges, a collection explicitly focused on high-quality experimental research in algorithms and data structures. (bookstore.ams.org) A 2020 historical review of experimental algorithmics describes it as a summary of Johnson’s reflections on how experimental algorithmics should be conducted and reported, and calls it “mandatory reading” for researchers in the area. (pesc.coppe.ufrj.br)
Its continued use is also visible in education and methodological guidance: it has been assigned as required reading in MIT algorithm-engineering courses and listed as recommended literature in university algorithm-engineering curricula. (jshun.csail.mit.edu) Later works on algorithm engineering, experimental methods, and guidelines for experimental algorithmics continue to cite it as a foundational reference. (doi.org) These sources support the conclusion that the paper’s principal impact has been methodological: it helped formalize expectations for credible, reproducible, comparable, and interpretable empirical evaluation of algorithms rather than introducing a specific algorithmic technique or industrial system.