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.