Volume 12 Number 12 (Dec. 2017)
Home > Archive > 2017 > Volume 12 Number 12 (Dec. 2017) >
JSW 2017 Vol.12(12): 946-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. 946-976, 2017.

General Information

ISSN: 1796-217X
Frequency: Monthly
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jsw@iap.org
  • Dec 22, 2017 News!

    Papers published in JSW Vol. 12, No. 1- Vol. 12, No. 11 have been indexed by DBLP.    [Click]

  • Dec 22, 2017 News!

    [CFP] 2018 the annual meeting of JSW Editorial Board, ICCSM 2018, will be held in Nice, France, July 17-19.   [Click]

  • Dec 22, 2017 News!

    Vol.12, No.6 has been indexed by EI (Inspec).    [Click]

  • Dec 29, 2017 News!

    Vol 12, No. 12 has been published with online version 6 original aritcles from 4 countries are published in this issue.      [Click]

  • Dec 22, 2017 News!

    Vol.12, No.7 has been indexed by EI (Inspec).   [Click]