From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 67C04BC75 for ; Fri, 25 Feb 2005 18:28:51 +0100 (CET) Received: from ptb-relay03.plus.net (ptb-relay03.plus.net [212.159.14.214]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j1PHSobc023742 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 25 Feb 2005 18:28:51 +0100 Received: from [80.229.56.224] (helo=chetara) by ptb-relay03.plus.net with esmtp (Exim) id 1D4jGk-000L0f-6R for caml-list@yquem.inria.fr; Fri, 25 Feb 2005 17:28:50 +0000 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Set union Date: Fri, 25 Feb 2005 17:30:12 +0000 User-Agent: KMail/1.7.1 References: <200502240920.04902.jon@jdh30.plus.com> <7f8e92aa05022502566909d86@mail.gmail.com> In-Reply-To: <7f8e92aa05022502566909d86@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200502251730.13003.jon@jdh30.plus.com> X-Miltered: at nez-perce with ID 421F6052.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 wrote:01 mistaken:01 stl:01 ocaml's:01 height:98 frog:98 contrast:01 short:01 behaviour:01 tree:02 tree:02 guess:02 seems:03 root:03 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: 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