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

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. [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. [2]. A. Levitin. Introduction to the Design and Analysis of Algorithms. 3e, Addison-Wesley, 2011. ISBN 978-0132316811.
3. [3]. Searching Arrays: Algorithms and Efficiency. Available from http://research.cs.queensu.ca/home/cisc121/2006s/webnotes/search.html (Accessed June, 2016).
4. [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. [5]. R. Sedgewick, Bundle of Algorithms in C++, Addison-Wesley, 2001, 3rd Edition.
6. [6]. Design and Analysis of Algorithms, Available from https://www.cs.cornell.edu/~kozen/papers/daa.pdf