Empirical Analysis on the Running Time of a Searching Algorithm, Chunk Algorithm

Year 2019, Volume: 3 Issue: 1, 24 - 29, 15.05.2019

Gazmend Xhaferi Florinda Imeri Flamure Sadiki Agon Memeti

Abstract

Searching and sorting, by no doubt, represent two
of the most fundamental and widely encountered problems in computer science.
Given a collection of objects, the goal of search is to find a particular
object in this collection or to recognize that the object does not exist in the
collection. A major goal of computer sciences is to understand and develop a
solution for the particular problem. 
Typically solving the problem involves at least four steps: (1) design
an algorithm, (2) analyze the correctness and efficiency of the procedure, (3)
implement that procedure in some programming language, and (4) test that
implementation.  An important issue is to
describe the efficiency of a given procedure for solving a problem. Informally,
usually we speak in terms of  “fast” or
“slow” programs, but the absolute execution time of an algorithm depends on
many factors such as: the size of the input, 
the programming language used to implement the algorithm, the quality of
the implementation and  the machine on
which the code is run (a supercomputer is faster than a laptop). In this paper
we will analyze the performances of a searching algorithm, precisely the chunk
algorithm. In analyzing the efficiency of chunk algorithm, we will only concentrate
on searching items, using the Chunk-Search Algorithm, on one-dimensional arrays
with integers. We wanted to see how does different chunk size, input size
(i.e., the “speed” of the algorithm as a function of the size of the input on
which it is run), and the machine on which the code is run. 

Keywords

chunk algorithm, computer performance, input size, chunk size

References

• [1]. Profs. Aslam & Fell, Analysis of Algorithms: Running Time September 7, 2005. Available from http://www.psnacet.edu.in/courses/MCA/Design%20and%20analysis%20of%20Algorithms/Lecture1.pdf
• [2]. A. Levitin. Introduction to the Design and Analysis of Algorithms. 3e, Addison-Wesley, 2011. ISBN 978-0132316811.
• [3]. Searching Arrays: Algorithms and Efficiency. Available from http://research.cs.queensu.ca/home/cisc121/2006s/webnotes/search.html (Accessed June, 2016).
• [4]. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Bentley, Programming Pearls, Addison-Wesley
• [5]. R. Sedgewick, Bundle of Algorithms in C++, Addison-Wesley, 2001, 3rd Edition.
• [6]. Design and Analysis of Algorithms, Available from https://www.cs.cornell.edu/~kozen/papers/daa.pdf