chap searching this is equal tonpn (need at least probesi= ( ( pn ( pn ( pn ( pn npn we require at least two probes to set the boundsso the cost is (need at least probesi= we now make take advantage of useful fact known as cebysev' inequality cebysev' inequality states that (need probes)or pi is pi < ( ) <( ) ( ) because ( < / this assumes uniformly distributed data thusthe expected number of probes is = < = ( = is this better than binary searchtheoretically yesbecause cost of (log log ngrows slower than cost of (log nhoweverwe have situation here which illustrates the limits to the model of asymptotic complexity in some practical situations yesc log does grow faster than log log in factits exponentially fasterbut even sofor practical input sizesthe absolute cost difference is fairly small thusthe constant factors might play role let' compare lg lg to lg lg lg lg difference