# RE: Searching missing number in large data.

*From*: "Mark W. Farnham" <mwf@xxxxxxxx>*To*: <abhishek.gurung@xxxxxxxxxxx>, "'Oracle Freelist'" <oracle-l@xxxxxxxxxxxxx>*Date*: Tue, 18 May 2010 11:34:24 -0400

Not sure why this didn't post earlier. From: Mark W. Farnham [mailto:mwf@xxxxxxxx] Sent: Tuesday, May 18, 2010 7:25 AM To: 'abhishek.gurung@xxxxxxxxxxx'; 'Oracle Freelist' Subject: RE: Searching missing number in large data. Okay, I'll play. But first I'd like to say this is a classic of missing information. First, you don't state the rule set for the algorithm (which is usually an infinite tape Turing machine in the computer world.) Second, the word "complexity" is ambiguous. Probably you mean "time" complexity or you actually mean "order of operations." Third, you do not state whether n is 2^32 or the number of missing numbers. Fourth, you do not state whether the file is already ordered. Fifth, we don't know whether we have a candidate list of missing numbers to check, or whether we must find all missing numbers in the range from 0 to 2^32. Sorting the input to begin with costs about n log n, where n is the approximate 2^32. So if you're looking for better than n log n, you must mean your initial list is sorted in some fashion, or else someone is pulling your leg. Now even if you had the "file" stored as a unique index in Oracle, I don't see how you can do better than n (being 2^32), where you attempt to insert each number from 0 to 2^32 and if it succeeds you know it was missing. Of course if you have a candidate list to check for being missing, then in this scenario n is only the length of your list of candidates. Am I missing something? mwf _____ From: oracle-l-bounce@xxxxxxxxxxxxx [mailto:oracle-l-bounce@xxxxxxxxxxxxx] On Behalf Of Abhishek Gurung Sent: Tuesday, May 18, 2010 5:20 AM To: Oracle Freelist Subject: Searching missing number in large data. Hi Problem: 1. There is a file containing numbers form 0 to 2^32 (2 raise to power 32). 2. About 1000 number missing in this range 3. An algo with complexity of log n to find the missing number. Regards Abhishek _____ From: oracle-l-bounce@xxxxxxxxxxxxx [mailto:oracle-l-bounce@xxxxxxxxxxxxx] On Behalf Of Abhishek Gurung Sent: Tuesday, May 18, 2010 5:20 AM To: Oracle Freelist Subject: Searching missing number in large data. Hi Problem: 1. There is a file containing numbers form 0 to 2^32 (2 raise to power 32). 2. About 1000 number missing in this range 3. An algo with complexity of log n to find the missing number. Regards Abhishek _____ The latest auto launches and test drives Drag n' drop <http://autos.in.msn.com/>

**References**:**Searching missing number in large data.***From:*Abhishek Gurung

## Other related posts:

- » Searching missing number in large data. - Abhishek Gurung
- » RE: Searching missing number in large data. - Bobak, Mark
- » Re: Searching missing number in large data. - Adam Musch
- » RE: Searching missing number in large data. - Mark W. Farnham
- » Re: Searching missing number in large data. - Jaromir D.B. Nemec
- » RE: Searching missing number in large data. - Abhishek Gurung
- » RE: Searching missing number in large data. - Taylor, Chris David
- » Re: Searching missing number in large data. - Nigel Thomas
- » Re: Searching missing number in large data. - Wayne Smith
- » Re: Searching missing number in large data. - Adam Musch
- » Re: Searching missing number in large data. - Nigel Thomas
- » Re: Searching missing number in large data. - Connor McDonald
- » RE: Searching missing number in large data. - Michael McMullen
- » Re: Searching missing number in large data. - Nigel Thomas
- » RE: Searching missing number in large data. - Michael McMullen
- » Re: Searching missing number in large data. - Christopher Boyle
- » Re: Searching missing number in large data. - Niall Litchfield
- » Re: Searching missing number in large data. - Jaromir D.B. Nemec