Re: [Caml-list] Set union

[Jon Harrop <jon@jdh30.plus.com>]

On Friday 25 February 2005 10:56, Radu Grigore wrote:
> 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.

Yes, my guess was O(n ln(n+N)) because the last insertions from the smaller 
set may be into a set with n+N elements. In contrast, the STL set_union 
function is T(n+N), which explains why it is so slow.

Now, what about best case behaviour: In the case of the union of two equal 
height, distinct sets, is OCaml's union T(1)?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://ffconsultancy.com