Measuring Algorithm Performance With Java: Patterns of Variation

摘要

Textbook coverage of algorithm performance emphasizes patterns of growth in expected and worst case execution times, relative to the size of the problem. Variability in execution times for a given problem size is usually ignored. In this research study, our primary focus is on the empirical distribution of execution times for a given algorithm and problem size. We examine CPU times for Java implementations of four sorting algorithms: selection sort, insertion sort, bubble sort, and quicksort. We measure variation in running times for these sorting algorithms. We show how the sort time distributions change as the problem size increases. With our methodology, we compare the relative stability of performance for the different sorting algorithms.