Archives of the Caml mailing list > Message from Radu Grigore

Browse thread

Set union

Jon Harrop
- Radu Grigore
  - Jon Harrop
    - Xavier Leroy
      - Jon Harrop
        
        Radu Grigore
        
        Radu Grigore
        
        Radu Grigore
        
        Jon Harrop

Date:	2005-02-25 (22:31)
From:	Radu Grigore <radugrigore@g...>
Subject:	Re: [Caml-list] Complexity of Set.union

On Fri, 25 Feb 2005 23:50:25 +0200, Radu Grigore <radugrigore@gmail.com> wrote:
> The complexity of set_union is indeed O(n+N), see [0]. 

Ah, BTW, if you do something like
  set_union(..., inserter(s));
where s is a set then inserter has logarithmic complexity so overall
you get O((n+N) lg(n+N)).

-- 
regards,
 radu
http://rgrig.blogspot.com/