Empirical analysis of binary search worst case on two personal computers using curve estimation technique

Abstract

Searching is one of the most basic and fundamental algorithms of the computer science. There are many types of searching technique e.g. Binary Search, Linear Search etc. Binary Search follows divide and conquer technique. The present study is an empirical analysis of Binary Search in the worst case on two personal computer having same hardware and software configurations. In this paper the objectives of the researchers are to find out that whether the two personal computers show identical behavior when performing Binary Search in the Worst Case scenario and to identify the best curve(s) along with its mathematical model(s) that can be fitted to the data points (Average Searching Time in the Worst case versus Number of Data Elements) for both the personal computers. The researchers have used simple Graphical representation, Mann-Whitney U test, Curve estimation technique, F-test and Residual analysis for this paper and came to the conclusion that both the personal computers exhibits different behavior in terms of execution time while performing Binary Search in the Worst Case scenario but both the datasets can be best fitted to Compound, Growth and Exponential curves.