Posteriori analysis of algorithms through derivations of growth rate based on frequency counts

• Main Author: Guzman, John Paul
• Format: text
• Language: English
• Published: Animo Repository 2016
• Subjects: Computer Sciences
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/2788
• Institution: De La Salle University

Literature has shown that apriori or posteriori estimates are used in order to determine the efficiency of algorithms. Apriori analysis determines the efficiency following the algorithm's logical structure while posteriori analysis accomplishes this by using data from calibrated experiments. The advantage of apriori analysis over posteriori is that it does not depend on other factors aside from the algorithm being analyzed. This makes it more thorough, but is limited by how powerful the current methods of mathematical analysis are. We present an empirical study involving posteriori analysis through the analysis of the measured frequency counts of a given algorithm. The developed method uses a series of formulas that extracts an approximation of the asymptotic behavior from the frequency count measurements. These formulas enable one to get an accurate insight on the asymptotic behavior of an algorithm without the need to do any manual computations or mathematical analysis. The method is initially tested on 26 Python programs involving iterative statements and recursive functions to establish the method's accuracy and correctness in determining programs' time complexity behavior. Results have shown that the developed method outputs accurate approximations of time complexity that correspond to manual apriori calculations.