Re: Union of sets in O(N)



Yes it is and i solved it.

On Jan 26, 3:05 pm, torb...@xxxxxxxxxxxxx (Torben Ægidius Mogensen)
wrote:
tome...@xxxxxxxxx writes:
Hi,

Suppose A,B,C.....are sets which containsrealnumbersbetween0 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 usehashtable to solve it but I wonder can I prove
from the above that ahashfunction withouthashcollision 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 samehashfunctionis O(1).

Torben

.