Polynomial curve fitting of execution time of binary search in worst case in personal computer

Abstract

Curve fitting is a well known method of data mining. This method can be used to identify the hidden patterns of any data set and thus may lead us to knowledge discovery. The present study fit the polynomial curves to the execution time (in nano-seconds) of binary search in worst case versus data size in a personal computer. Data size varies from one thousand (1000) to twenty thousand (20000) with an interval of five hundred (500). For each data size one thousand (1000) observations have been collected and to discard the outliers from the observations, two-step clustering algorithm have been employed. The mean value of the largest cluster for each data size gives us the mean execution time (in nano-seconds) for the respective data size. Polynomial curve fitting has been employed on the data points and candidate models are identified based on the values of Adjusted R-Squared, Residual Standard Error and Root Mean Square Error. Two (2) separate information criteria – AIC and BIC have been used to find out the best polynomial curves that fit the data points. It has been observed that polynomial of degree 24 comes out to be the best curve using AIC and polynomial of degree 22 becomes best curve using BIC.