This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

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: 2007-06-27 (21:24) From: Pal-Kristian Engstad Subject: Re: [Caml-list] Book about functional design patterns
```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.

--