Re: [Caml-list] Book about functional design patterns

[Pal-Kristian Engstad <pal_engstad@naughtydog.com>]

Quôc Peyrot wrote:
>
> On Jun 27, 2007, at 10:58 PM, Pal-Kristian Engstad wrote:
>
>> 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.
>
> 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.

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