Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!dsinc!ub!sarnath
From: sarnath@acsu.buffalo.edu (Ramnath Sarnath)
Newsgroups: comp.theory
Subject: Re: lower-bound for binary search
Message-ID: <56707@eerie.acsu.Buffalo.EDU>
Date: 29 Jan 91 19:52:19 GMT
References: <56531@eerie.acsu.Buffalo.EDU>
Sender: news@acsu.Buffalo.EDU
Organization: State University of New York at Buffalo/Comp Sci
Lines: 18
Nntp-Posting-Host: sybil.cs.buffalo.edu

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