Version franaise
Home About Download Resources Contact us
Browse thread
The Implicit Accumulator: a design pattern using optional arguments
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Pal-Kristian Engstad <pal_engstad@n...>
Subject: Re: [Caml-list] Book about functional design patterns
Quc Peyrot wrote:
>
> On Jun 27, 2007, at 10:58 PM, Pal-Kristian Engstad wrote:
>
>> Quc 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.
>
> Oops, my mistake I meant "floor" not ceil.
>
>> So you are saying that inserting N elements into a tree takes 
>> O(n*log2(n)).
>
> Not exactly, log2(N!) is a closer estimate (estimate because of the 
> "floor" introducing a bias in the sum)
No, no. Let's assume it always touches log2(n) elements, where n goes 
from 1 .. N. Then we have:

    time = C * log2(1) + C * log2(2) + C * log2(3) + .... + C * log N = 
C * (log2(1) + ... + log2(N) <= C * N * log2(N),

since

    log(n) <= log(N).

Thanks,

PKE.

-- 
Pl-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