Set union
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20050225 (17:48) 
From:  Xavier Leroy <Xavier.Leroy@i...> 
Subject:  Re: [Camllist] Set union 
[ Complexity of Set.union ] > > For other cases > > the process is a bit more complex: take the root of the short tree, > > split the large tree into smaller/larger elements based on that root, > > compute union of "small" trees, "compute union of "large" trees", > > merge them. If I'm not mistaken this is O(m lg n) too. My hope is that union takes time O(N log N) where N is the sum of the numbers of elements in the two sets. I'm thoroughly unable to prove that, though, in particular because the complexity of the "split" operation is unclear to me. This bound is "reasonable", however, in that the trivial union algorithm (repeatedly add every element of one of the sets to the other one) achieves this bound, and the trick with "joining" is, intuitively, just an optimization of this trivial algorithm. > Now, what about best case behaviour: In the case of the union of two equal > height, distinct sets, is OCaml's union T(1)? Did you mean "of two equal height sets such that all elements of the first set are smaller than all elements of the second set"? That could indeed run in constant time (just join the two sets with a "Node" constructor), but I doubt the current implementation achieves this because of the repeated splitting.  Xavier Leroy