Re: [Caml-list] Set union

[Xavier Leroy <Xavier.Leroy@inria.fr>]

[ 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