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

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/>

```