From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id EE7C7BC6B for ; Wed, 27 Jun 2007 23:18:23 +0200 (CEST) Received: from smtp2a.orange.fr (smtp2a.orange.fr [80.12.242.139]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5RLINMA022051 for ; Wed, 27 Jun 2007 23:18:23 +0200 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf2a06.orange.fr (SMTP Server) with ESMTP id 7D3BF700008E for ; Wed, 27 Jun 2007 23:18:23 +0200 (CEST) Received: from [192.168.1.162] (ALagny-153-1-98-23.w90-3.abo.wanadoo.fr [90.3.145.23]) by mwinf2a06.orange.fr (SMTP Server) with ESMTP id 49176700008A; Wed, 27 Jun 2007 23:18:23 +0200 (CEST) X-ME-UUID: 20070627211823299.49176700008A@mwinf2a06.orange.fr In-Reply-To: <4682CF58.7010709@naughtydog.com> References: <200706271314.35134.jon@ffconsultancy.com> <1A1D6F56-B3DB-4552-969C-9859482175AC@lrde.epita.fr> <46826C69.5060802@functionality.de> <20070627191633.73ab011a@kerneis.info> <342AAB2F-A76C-42C8-A5F1-4139BE2FE4A9@lrde.epita.fr> <4682BF04.8090606@janestcapital.com> <4682CA02.4040006@janestcapital.com> <25B2FF5F-7C58-4F70-B1AE-0FD7577FB521@lrde.epita.fr> <4682CF58.7010709@naughtydog.com> Mime-Version: 1.0 (Apple Message framework v752.2) Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Message-Id: Cc: caml-list@yquem.inria.fr Content-Transfer-Encoding: quoted-printable From: =?ISO-8859-1?Q?Qu=F4c_Peyrot?= Subject: Re: [Caml-list] Book about functional design patterns Date: Wed, 27 Jun 2007 23:18:21 +0200 To: Pal-Kristian Engstad X-Mailer: Apple Mail (2.752.2) X-Miltered: at concorde with ID 4682D41F.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; lrde:01 node:01 node:01 inserting:01 2007,:98 wrote:01 wrote:01 caml-list:01 oops:01 tree:02 functional:02 pal-kristian:03 engstad:04 meant:06 jun:09 On Jun 27, 2007, at 10:58 PM, Pal-Kristian Engstad wrote: > Qu=F4c Peyrot wrote: >> I don't understand that part. Each time you add a node, log2(n) =20 >> node needs to be re-allocated. Hence the total number of =20 >> reallocations is: >> Sum(ceil(log2(i)), i =3D 1..N) with N =3D 1000000, which is = significant. Oops, my mistake I meant "floor" not ceil. > So you are saying that inserting N elements into a tree takes O=20 > (n*log2(n)). Not exactly, log2(N!) is a closer estimate (estimate because of the =20 "floor" introducing a bias in the sum) --=20 Best Regards, Qu=F4c