A COMPARATIVE STUDY OF FUNDAMENTAL ALGORITHMS IN DATA STRUCTURES

Well Researched and Ready to use Ph.D Thesis, page numbers: 154, Department: Ph.D Computer Science

ABSTRACT 

Searching is a fundamental algorithm that is often used in computation. The need for searching items, records and files from among several objects occur frequently in data processing, which could range from commercial, educational to scientific. Of all existing search algorithms used, the binary search is regarded as the most efficient numerically for pragmatic purposes. It is an efficient searching technique for sorted data. But there are variations in the O-notation (Big O notation) of sorting methods. There is a need to know whether these variations affect the efficiency of the binary search algorithm. The linear search algorithm on the other hand, is not dependent on sorting but it is inefficient; it is of order O(N). The aim of this study was therefore to conduct a comparative analysis of these fundamental algorithms when subjected to some experimental platforms. The specific objectives of the study were to: i. compare the efficiency of binary search algorithm with that of the linear search algorithm through simulation using different sizes of randomly-generated data; ii. examine new information concerning the efficiency of binary search strategy; iii. propose an informed statement on search algorithms; and iv. develop a better search algorithm to take care of plausible shortcomings. The method of simulating binary search algorithm using twenty numerical data sets that were randomly generated was employed. The size of the sets ranged from 50 to 400,000. A computer program to simulate and capture the time complexities of both the binary and linear search strategies was developed to compare their efficiency. The findings of this study revealed that: i. binary search algorithm cannot always be regarded as the most efficient when the sorting time complexity is taken into consideration; when the sorting time was considered with the search time, the linear search was found to be more efficient than the binary search; ii. dependency of the efficiency of binary search on the type of sorting algorithm used was immeasurable; that is, when there was no efficient sorting algorithm in place, the binary search was found to be worthless; iii. with repeated use of the binary search on a specific sorted data, the binary search gradually recovers to take over as the better performing search algorithm in terms of time complexity than the linear search; thus, making the binary search more appealing than the linear search; and iv. Bilinear recursive search algorithm was developed, which, worked on unsorted data and performed better than the traditional linear search method. The study concluded that the Bilinear recursive search algorithm provided a more efficient search algorithm that can be used on unsorted data, yet compete favourably with the binary search and any of the other popular search techniques in existence. Thus, the study recommended that the search algorithm be adopted by data processing units in educational institutions, government establishments, commercial outfits, among others.

Order the Complete Ph.D Thesis

Share with your friends