ALCOMFT-TR-01-80

Catherine Mc Geoch, Peter Sanders, Rudolf Fleischer, Paul R. Cohen and Doina Precup
Searching for Big-Oh in the Data: Inferring Asymptotic Complexity from Experiments
MPI. Work package 5. May 2001.

Abstract: The complexity analysis of algorithms is one of the core activities of computer scientists, especially in the branch of theoretical computer science known as algorithmics. The ultimate goal would be to find closed form expressions for the runtime (or other measures of resource consumption), in terms of input parameters of interest. Since this is usually too complicated, we are often content with asymptotic expressions for the worst case performance depending on a small number of input parameters like problem size, which are usually presented in O(·)-notation. Even this task can be very difficult so it is important to use all available tools.

In this paper we investigate the empirical version of this primary activity - how to find asymptotic trends in data obtained from experimental studies of algorithms. We illustrate both the promise and the difficulties inherent in the use of experiments to suggest, support, and refute hypotheses about asymptotic behavior.

Postscript file: ALCOMFT-TR-01-80.ps.gz (150 kb).