This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Set union
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2005-02-25 (17:28) From: Jon Harrop Subject: Re: [Caml-list] Set union
```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

```