sarnath@sybil.cs.Buffalo.EDU (Ramnath Sarnath) (01/29/91)
I am looking for a proof that binary search cannot be done in time faster than O(logn). Could anyone give me a ref.? sarnath
jg@prg.ox.ac.uk (Jeremy Gibbons) (01/29/91)
sarnath@sybil.cs.Buffalo.EDU (Ramnath Sarnath) asks: > I am looking for a proof that binary search cannot be done in time > faster than O(logn). Could anyone give me a ref.? Surely this is in just about every Design and Analysis of Algms text? There are n+1 possible outcomes (n positions plus one `not here'), or 2n+1 if you want to say where the object should go in an unsuccessful search. Now k comparisons will distinguish between 2^k situations. The information-theoretic lower bound on the number of comparisons is thus log(n+1) (or log(2n+1)). In short, I would say the reference should be `general knowledge'! *-----------------------------------------------------------------------* | Jeremy.Gibbons@prg.oxford.ac.uk PRG, 11 Keble Road, Oxford, UK | *-----------------------------------------------------------------------*
edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.)) (01/30/91)
In article <56531@eerie.acsu.Buffalo.EDU>, sarnath@sybil.cs.Buffalo.EDU (Ramnath Sarnath) writes: >I am looking for a proof that binary search cannot be done in time >faster than O(logn). Could anyone give me a ref.? Refer to this message. A binary search by definition repeatedly chooses between one of two alternatives. If k such choices are made, there are 2^k possible outcomes. Therefore, at most 2^k possible items can be selected from with k operations. At least log-base-2 of n operations must be performed to select from n items. -- edp (Eric Postpischil) "Always mount a scratch monkey." edp@jareth.enet.dec.com
sarnath@acsu.buffalo.edu (Ramnath Sarnath) (01/30/91)
In article <56531@eerie.acsu.Buffalo.EDU> I wrote: > >I am looking for a proof that binary search cannot be done in time >faster than O(logn). Could anyone give me a ref.? > > >sarnath This needs a clarification... what I wanted to prove was that searching a sorted sequence (by any means) is not possible in time faster than O(logn). sorry about the mix-up. sarnath PS : thanx for all the responses
raoult@irisa.fr (Jean-Claude Raoult) (01/30/91)
I am not so sure, that a lower bound for an algorithm searching in a sorted list "by all means" can exist. If your means is divination, then your search can be done in O(1). More seriously, it may happen that your sorted list is at the same time a h-code table filled with a perfect hashing function. Then again, you will get your answer in O(1). If the only thing you know is that your list is sorted, then you must use only comparisons - hence the log(n) bound.