Average-Case Lower Bounds for Searching
Colin McDiarmid · SIAM Journal on Computing · 1988
Lower bounds are given for certain average search times in a set with a random linear order about which there is partial information. These bounds extend various recent worst-case and average-case results, in particular those of Alt and Mehlhorn, Borodin et al., and Mairson concerning searching “semi-sorted” tables and trade-offs between presorting time and search time. We make fuller use of the framework of information theory than have previous investigations.