On Thu, 24 Feb 2005 09:20:04 +0000, Jon Harrop <jon@jdh30.plus.com> wrote:
> 
> Following my last post about the speed of set union in OCaml compared to
> C++/STL. What is the complexity of set union in OCaml in terms of the number
> of elements and the number of comparisons?

As no one gave an informed answer I'll risk a hand-waiving one.

When all elements of a set are bigger than all elements of the other
set the Set.union function seems to simply add the elements of the
small set to the bigger set one at a time. So the complexity looks
like O(m lg n) where m is the size of the smaller set. 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.

-- 
regards,
 radu
http://rgrig.blogspot.com/