sasha mal wrote:
> Currently,
> 
> Set.inter x y
> 
> splits y into two trees, one containing elements that are bigger and
> the other containing elements that are smaller than the top of x,
> then applies the procedure recursively. What is the exact runtime of
> the algorithm? Is there a better one for the intersection for OCaml
> sets?

The general algorithm is linear in the size of both sets in the worst 
case, however it can be quite a bit faster in many circumstances.  See 
the paper "Implementing Sets Efficiently in a Functional Language" by 
Stephen Adams[1] for a more detailed discussion.  I haven't looked at 
INRIA's exact implementation very closely, so they may do some extra 
tricks not discussed there, but it certainly appears to use this general 
technique.

-Mike

[1] - http://citeseer.ist.psu.edu/162336.html