On Jun 27, 2007, at 11:18 PM, Pal-Kristian Engstad wrote:

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

I think we agree, I'm just saying that C*N*log2(N) is a over- 
estimated upper bound for large N.

C*(log2(1) + ... + log2(N)) = C * log2(1*2*....*N) = C * log2(N!)
hence

time <= C*log2(N!) <= C * N * log2(N)

as an example, for N = 100

sum(floor(log2(i)), i = 1..100) = 480
log2(100!) = 524 (overestimated by 10%)
100 * log2(100) = 664 (overestimated by 40%)

for large N, the difference is going to be significant.

But anyway, the details doesn't matter, it just looks to me that  
inserting N elements in a functional map, is really significant.
If my maths are correct, for only 1000 elements, we are going to have  
an extra 8500 allocations (the difference is so huge I actually can't  
believe my maths...)

-- 
Best Regards,
Quôc