Author |
Topic: Search in O(1) (Read 764 times) |
|
mad
Junior Member
Posts: 118
|
 |
Search in O(1)
« on: Mar 9th, 2008, 9:24am » |
 Quote  Modify
|
Determine existence or non-existence of a number in a sorted list of N numbers where N numbers range over M, M>>N. N is very large to span multiple disks. Find it O(1).
|
|
 IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Search in O(1)
« Reply #1 on: Mar 9th, 2008, 9:50am » |
Quote Modify
|
Another Question-
Given an array of R,G and B balls, arrange them in groups with all R together, G together anb B together in one scan.
I thought of keeping the counts of all the three and building a new array based on this. Some better method, say inplace or more space efficient?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Search in O(1)
« Reply #2 on: Mar 9th, 2008, 1:44pm » |
Quote Modify
|
on Mar 9th, 2008, 9:50am, mad wrote:| Given an array of R,G and B balls, arrange them in groups with all R together, G together anb B together in one scan. |
|
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1100111371
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Search in O(1)
« Reply #3 on: Mar 12th, 2008, 10:33am » |
Quote Modify
|
on Mar 9th, 2008, 9:24am, mad wrote:| Determine existence or non-existence of a number in a sorted list of N numbers where N numbers range over M, M>>N. N is very large to span multiple disks. Find it O(1). |
|
Woud N be O(1)?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Search in O(1)
« Reply #4 on: Mar 12th, 2008, 1:28pm » |
Quote Modify
|
on Mar 9th, 2008, 9:24am, mad wrote:| Determine existence or non-existence of a number in a sorted list of N numbers where N numbers range over M, M>>N. N is very large to span multiple disks. Find it O(1). |
|
I have problems with English ... are you asking ... is there a number on the list ... meaning is the list nonempty? Or are you looking for given number?
First can be answered in O(1), second requires at least log (N) comparisons (in the average case).
|
| « Last Edit: Mar 12th, 2008, 1:29pm by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print