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=1.1 required=5.0 tests=AWL,RCVD_IN_WHOIS_BOGONS autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id AA307BC6B for ; Wed, 27 Jun 2007 23:04:29 +0200 (CEST) Received: from sdmx1.scea.com (sdmx1.scea.com [160.33.44.36]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5RL4SeI015280 for ; Wed, 27 Jun 2007 23:04:29 +0200 Received: from edenfox.989studios.com (edenfox.989studios.com [160.33.45.60]) by sdmx1.scea.com (8.13.6/8.13.1) with ESMTP id l5RL3nJH031426; Wed, 27 Jun 2007 14:03:49 -0700 X-Envelope-From: X-Envelope-To: X-Envelope-To: Received: from postal1-dog.naughtydog.com (testmail.naughtydog.com [10.15.0.5]) by edenfox.989studios.com (8.13.7/8.13.7/SCEAint-1.0) with ESMTP id l5RL3m7x008672; Wed, 27 Jun 2007 14:03:48 -0700 Received: from [127.0.0.1] ([150.0.6.116]) by postal1-dog.naughtydog.com with Microsoft SMTPSVC(6.0.3790.3959); Wed, 27 Jun 2007 14:02:37 -0700 Message-ID: <4682CF58.7010709@naughtydog.com> Date: Wed, 27 Jun 2007 13:58:00 -0700 From: Pal-Kristian Engstad User-Agent: Thunderbird 1.5.0.12 (Windows/20070509) MIME-Version: 1.0 To: =?ISO-8859-1?Q?Qu=F4c_Peyrot?= Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Book about functional design patterns 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> In-Reply-To: <25B2FF5F-7C58-4F70-B1AE-0FD7577FB521@lrde.epita.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-OriginalArrivalTime: 27 Jun 2007 21:02:37.0107 (UTC) FILETIME=[7D8EE830:01C7B8FE] X-Scanned-By: MIMEDefang 2.48 on 160.33.44.36 X-Scanned-By: MIMEDefang 2.62 on 160.33.45.60 X-BorderEnvelope-To: X-BorderEnvelope-To: X-Miltered: at discorde with ID 4682D0DC.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; node:01 node:01 inserting:01 iterating:01 pke:01 dog:98 wrote:01 caml-list:01 essentially:02 tree:02 tree:02 graphics:02 functional:02 pal-kristian:03 engstad:04 Quôc Peyrot wrote: > I don't understand that part. Each time you add a node, log2(n) node > needs to be re-allocated. Hence the total number of reallocations is: > Sum(ceil(log2(i)), i = 1..N) with N = 1000000, which is significant. So you are saying that inserting N elements into a tree takes O(n*log2(n)). > Where is my mistake in these maths? No mistake. After all, after insertion you essentially have a sorted tree, since iterating the tree takes O(n). Sorting take O(n*log n)... Thanks, PKE. -- Pål-Kristian Engstad (engstad@naughtydog.com), Lead Graphics & Engine Programmer, "Uncharted"-team, Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North, Santa Monica, CA 90404, USA. Ph.: (310) 633-9112. "Most of us would do well to remember that there is a reason Carmack is Carmack, and we are not Carmack.", Jonathan Blow, 2/1/2006, GD Algo Mailing List