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 (10:56) 
From:  Radu Grigore <radugrigore@g...> 
Subject:  Re: [Camllist] Set union 
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 handwaiving 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/