Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!uunet!mcsun!ukc!ox-prg!culhua!jg From: jg@prg.ox.ac.uk (Jeremy Gibbons) Newsgroups: comp.theory Subject: Re: lower-bound for binary search Message-ID: Date: 29 Jan 91 12:03:12 GMT References: <56531@eerie.acsu.Buffalo.EDU> Sender: news@prg.ox.ac.uk Organization: Oxford University Computing Laboratory, UK Lines: 16 In-reply-to: sarnath@sybil.cs.Buffalo.EDU's message of 28 Jan 91 20:53:38 GMT 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 | *-----------------------------------------------------------------------*