Re: Searching missing number in large data.
- From: "Jaromir D.B. Nemec" <jaromir@xxxxxxxxxxxx>
- To: <ahmusch@xxxxxxxxx>, <abhishek.gurung@xxxxxxxxxxx>, <niall.litchfield@xxxxxxxxx>, <mcdonald.connor@xxxxxxxxx>, <nigel.cl.thomas@xxxxxxxxxxxxxx>
- Date: Sat, 22 May 2010 17:11:36 +0200
Hello,
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.
There is for sure a solution for this problem.
Unfortunately this solution is viable only in case on an examination
question (as mentioned in a previous post).
You can showin the examination that
a) you understand logarithms and (probably more important)
b) you can solve problems in a non-conventional way.
The key to solve this problem is than the N is fixed. (N = 2^^32).
This is not very common in case of examining complexity of algorithms.
In other words you are not interested in scaling of the algorithm with
increasing N, but only in the behaviour for a fixed value of N.
To solve the problem is as easy as to find an appropriate base of logarithm,
so that the value of the logarithm is equal 2 * N for N = 2^^32.
Log(base, 2^^32) = 2 * 2^^32
To find the base requires only some elementary math.
I'm not going in details here.
Base = 1.0000000025821745
You use the algorithm mentioned several times in this thread with
the complexity of O(2*N) and you can claim (for N = 2^^32)
that *this* algorithm has the complexity of O(log(N)) using logarithm with
the base above.
Prove
select log(1.0000000025821745,power(2,32)) from dual;
LOG(1.0000000025821745,POWER(2,32))
-----------------------------------
8589934493,797952647757780776878894193829
1 rows selected
which is circa 2 * 2^^32 = 2*N
regards
Jaromir D.B. Nemec
--
//www.freelists.org/webpage/oracle-l
Other related posts:
