Volume 12 Number 12 (Dec. 2017)
Home > Archive > 2017 > Volume 12 Number 12 (Dec. 2017) >
JSW 2017 Vol.12(12): 964-976 ISSN: 1796-217X
doi: 10.17706/jsw.12.12.946-976

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

John Paul Guzman*, Teresita Limoanco

College of Computer Studies, De La Salle University-Manila, Manila, Philippines.

Abstract—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.

Index Terms—Algorithm analysis, time complexity, asymptotic notations, empirical algorithmics.

[PDF]

Cite: John Paul Guzman*, Teresita Limoanco, "An Empirical Approach to Algorithm Analysis Resulting in Approximations to Big Theta Time Complexity," Journal of Software vol. 12, no. 12, pp. 964-976, 2017.

General Information

ISSN: 1796-217X (Online)
Frequency:  Quarterly
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, CNKIGoogle Scholar, ProQuest, INSPEC(IET), ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsweditorialoffice@gmail.com
  • Mar 01, 2024 News!

    Vol 19, No 1 has been published with online version    [Click]

  • Apr 26, 2021 News!

    Vol 14, No 4- Vol 14, No 12 has been indexed by IET-(Inspec)     [Click]

  • Nov 18, 2021 News!

    Papers published in JSW Vol 16, No 1- Vol 16, No 6 have been indexed by DBLP   [Click]

  • Jan 04, 2024 News!

    JSW will adopt Article-by-Article Work Flow

  • Nov 02, 2023 News!

    Vol 18, No 4 has been published with online version   [Click]