Needed: An empirical science of algorithms

Deductive algorithmic science has reached a high level of sophistication, but its worst-case and average-case results seldom tells one how well an algorithm is actually going to work in practice. The paper argues that an empirical science of algorithms is a viable alternative. It responds to misgivings about an empirical approach, including the prevalent notion that only a deductive treatment can be ‘theoretical’ or sophisticated. NP-completeness theory, for instance, is interesting partly because it has significant, if unacknowledged, empirical content. An empirical approach requires not only rigorous experimental design and analysis, but also the invertion of empirically-based explanatory theories. The paper gives some examples of recent work that partially achieves this aim.