wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Search in O(1)
        
(Message started by: mad on Mar 9^th, 2008, 9:24am)

Title: Search in O(1)
Post by mad on Mar 9^th, 2008, 9:24am

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).

Title: Re: Search in O(1)
Post by mad on Mar 9^th, 2008, 9:50am

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.

[hide]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?[/hide]

Title: Re: Search in O(1)
Post by towr on Mar 9^th, 2008, 1:44pm

on 03/09/08 at 09:50:44, 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

Title: Re: Search in O(1)
Post by Grimbal on Mar 12^th, 2008, 10:33am

on 03/09/08 at 09:24:27, 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)?

Title: Re: Search in O(1)
Post by Hippo on Mar 12^th, 2008, 1:28pm

on 03/09/08 at 09:24:27, 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).