Bounds for the sample size in performance testing of combinatorial algorithms

by Vesa P. Vaskelainen and Vesa Riihimaki.

Abstract: The performance of combinatorial algorithms is often evaluated by using the computational times of a certain number of inputs. The run times of algorithms with certain type of data appear in computational results as the mean of a small sample. Still the choice of sample size is rarely based on the distribution of run times. In this work we use statistical tests to compare the performance of combinatorial algorithms. Furthermore, we determine confidence intervals for the run times of combinatorial algorithms. As a consequence, we get easy-to-use bounds of sample size for justifying the accuracy of computational results.

Key Words: Confidence interval, combinatorial algorithms, CPU performance, normal approximation, normality, statistical tests, skewness

Vesa P. Vaskelainen,
Vesa Riihimaki,

Editor: David D. Hanagal,

READING THE ARTICLE: You can read the article in portable document (.pdf) format (165176 bytes.)

NOTE: The content of this article is the intellectual property of the authors, who retains all rights to future publication.

This page has been accessed 2587 times since JULY 28, 2009.

Return to the InterStat Home Page.