Re: Union of sets in O(N)
- From: torbenm@xxxxxxxxxxxxx (Torben Ægidius Mogensen)
- Date: Fri, 26 Jan 2007 14:05:22 +0100
tomerdr@xxxxxxxxx writes:
Hi,
Suppose A,B,C.....are sets which contains real numbers between 0 and 1,
(U=Union)
I need to create a set S= AUBUCU...... in O(N)
It is also known that for every x,y belong to S
MIN(ABS(X-Y))>1/m (x!=y)
Where 1/m=O(N)
Don't you mean m=O(N)? Otherwise, this is trivially false.
I am planning to use hash table to solve it but I wonder can I prove
from the above that a hash function without hash collision exist?
This sounds like homework to me. I'll give you a hint: Use floor(X*N)
as "hash" function. Then show that the maximal number of elements that
have the same hash function is O(1).
Torben
.
- Follow-Ups:
- Re: Union of sets in O(N)
- From: tomerdr
- Re: Union of sets in O(N)
- References:
- Union of sets in O(N)
- From: tomerdr
- Union of sets in O(N)
- Prev by Date: Union of sets in O(N)
- Next by Date: Re: Hofman and Diaby talk about P=NP at INFORMS 2007
- Previous by thread: Union of sets in O(N)
- Next by thread: Re: Union of sets in O(N)
- Index(es):
Relevant Pages
|
