Visualization of binary search in worst case using spline interpolation curve fitting in personal computer

Abstract

The paper aims to visualize the performance of binary search algorithm in the worst case scenario in a personal computer (laptop) using spline interpolation curve fitting. The researchers have chosen Linux operating system and OpenJDK runtime environment for simulating the binary search algorithm in the worst case and have run the java code of binary search for data size one thousand to twenty thousand with an interval of five hundred. For each data size one thousand observations have been noted. To eliminate and/or minimize the effect of outliers (if any) from the observations for each data size three different approaches have been employed in this paper. These approaches are (i) calculation of mean execution time for each data size, (ii) identifying the largest cluster of execution time for each data size by using Two-step clustering and finding the mean value of the largest cluster for each data size and (iii) identifying the center of the largest cluster of execution time for each data size by using K-means clustering where K = 2. At the end, three different spline interpolation curves have been obtained for each of these three cases and we observe that all of them display different patterns.