An Empirical Approach to Algorithm Analysis Resulting in Approximations to Big Theta Time Complexity

摘要

Literature has shown that apriori or posteriori estimates are used in order to determine efficiency of algorithms. Apriori analysis determines the efficiency following algorithm’s logical structure, while posteriori analysis accomplishes this by using data from experiments. Apriori analysis has two main advantages over posteriori analysis: a.) it does not depend on other factors aside from the algorithm being analyzed; b.) it naturally produces measurements in terms of asymptotic notations. These advantages result in thorough and more generalizable analysis. However, apriori techniques are limited by how powerful the current methods of mathematical analysis are. This paper presents a posteriori method that outputs time complexity measured in Big Theta notation. The developed method uses a series of formulas and heuristics to extract an algorithm’s asymptotic behavior solely from its frequency count measurements. The method was tested on 30 Python programs involving arithmetic operations, iterative statements, and recursive functions to establish its accuracy and correctness in determining time complexity behavior. Results have shown that the developed method outputs precise approximations of time complexity that are expected from manual apriori calculations.