Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!samsung!zaphod.mps.ohio-state.edu!ncar!csn!ub!sarnath
From: sarnath@sybil.cs.Buffalo.EDU (Ramnath Sarnath)
Newsgroups: comp.theory
Subject: lower-bound for binary search
Message-ID: <56531@eerie.acsu.Buffalo.EDU>
Date: 28 Jan 91 20:53:38 GMT
Sender: news@acsu.Buffalo.EDU
Organization: State University of New York at Buffalo/Comp Sci
Lines: 6
Nntp-Posting-Host: sybil.cs.buffalo.edu
Originator: sarnath@sybil.cs.Buffalo.EDU


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