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

Date of Publication

2016

Document Type

Bachelor's Thesis

Degree Name

Bachelor of Science in Computer Science

Subject Categories

Computer Sciences

College

College of Computer Studies

Department/Unit

Computer Science

Thesis Adviser

Teresita Limoanco

Defense Panel Chair

Solomon See

Defense Panel Member

Arnulfo Azcarraga

Abstract/Summary

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.

Abstract Format

html

Language

English

Format

Electronic

Accession Number

CDTG006745

Shelf Location

Archives, The Learning Commons, 12F, Henry Sy Sr. Hall

Physical Description

1 computer optical disc ; 4 3/4 in.

Upload Full Text

wf_no

This document is currently not available here.

Share

COinS