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:28) 
From:  Jon Harrop <jon@j...> 
Subject:  Re: [Camllist] 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