Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!apple!agate!ucbvax!bloom-beacon!deccrl!news.crl.dec.com!shlump.nac.dec.com!jareth.enet.dec.com!edp
From: edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.))
Newsgroups: comp.theory
Subject: Re: lower-bound for binary search
Message-ID: <19559@shlump.nac.dec.com>
Date: 29 Jan 91 16:13:35 GMT
References: <56531@eerie.acsu.Buffalo.EDU>
Sender: newsdaemon@shlump.nac.dec.com
Reply-To: edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.))
Organization: Digital Equipment Corporation
Lines: 17

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