Linear Search Versus Binary Search: A Statistical Comparison for Binomial Inputs

摘要

For certain algorithms such as sorting and searching, the parameters of the input probability distribution, in addition to the size of the input, have been found to influence the complexity of the underlying algorithm. The present paper makes a statistical comparative study on parameterized complexity between linear and binary search algorithms for binomial inputs.