From: "Quôc Peyrot" <chojin@lrde.epita.fr>
To: Pal-Kristian Engstad <pal_engstad@naughtydog.com>
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Book about functional design patterns
Date: Wed, 27 Jun 2007 23:18:21 +0200 [thread overview]
Message-ID: <C1E56D74-E1D0-4CC0-B1BE-3B7B67BBA0D2@lrde.epita.fr> (raw)
In-Reply-To: <4682CF58.7010709@naughtydog.com>
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)
--
Best Regards,
Quôc
next prev parent reply other threads:[~2007-06-27 21:18 UTC|newest]
Thread overview: 60+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-06-27 12:14 The Implicit Accumulator: a design pattern using optional arguments Jon Harrop
2007-06-27 13:18 ` [Caml-list] " Quôc Peyrot
2007-06-27 13:53 ` Jon Harrop
2007-06-27 14:18 ` Thomas Fischbacher
2007-06-27 15:09 ` Quôc Peyrot
2007-06-27 15:28 ` Mattias Engdegård
2007-06-27 15:38 ` Robert Fischer
2007-06-27 15:48 ` Mattias Engdegård
2007-06-27 16:01 ` Robert Fischer
2007-06-27 16:01 ` Mattias Engdegård
2007-06-27 18:06 ` Jon Harrop
2007-06-27 18:31 ` Brian Hurt
2007-06-27 19:56 ` skaller
2007-06-27 20:17 ` Jonathan Bryant
2007-06-27 22:57 ` Jon Harrop
2007-06-27 16:53 ` Hash-consing (was Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments) Daniel Bünzli
2007-06-30 8:19 ` [Caml-list] The Implicit Accumulator: a design pattern using optional arguments Pierre Etchemaïté
2007-06-27 13:55 ` Thomas Fischbacher
2007-06-27 15:06 ` Quôc Peyrot
2007-06-27 15:53 ` Jon Harrop
2007-06-28 11:01 ` Thomas Fischbacher
2007-06-28 11:32 ` Jon Harrop
2007-06-28 11:42 ` Joel Reymont
2007-06-28 12:08 ` Jon Harrop
2007-06-28 13:10 ` Quôc Peyrot
2007-06-28 13:35 ` Thomas Fischbacher
2007-06-28 12:59 ` Thomas Fischbacher
2007-06-28 13:05 ` Jon Harrop
2007-06-28 13:33 ` Thomas Fischbacher
2007-06-28 14:43 ` Jon Harrop
2007-06-28 16:01 ` Thomas Fischbacher
2007-06-28 17:53 ` Jon Harrop
2007-06-27 16:39 ` Thomas Fischbacher
2007-06-27 19:26 ` Quôc Peyrot
2007-06-28 11:39 ` Thomas Fischbacher
2007-06-28 14:44 ` Jon Harrop
2007-06-28 16:03 ` Thomas Fischbacher
2007-06-28 17:20 ` Dirk Thierbach
2007-06-28 22:12 ` Thomas Fischbacher
2007-06-29 1:10 ` Jon Harrop
2007-06-29 10:55 ` Thomas Fischbacher
2007-06-29 6:12 ` Dirk Thierbach
2007-06-27 17:16 ` Book about functional design patterns Gabriel Kerneis
2007-06-27 17:48 ` [Caml-list] " Jon Harrop
2007-06-27 19:33 ` Quôc Peyrot
2007-06-27 19:30 ` Quôc Peyrot
2007-06-27 19:48 ` Brian Hurt
2007-06-27 20:04 ` Quôc Peyrot
2007-06-27 20:35 ` Brian Hurt
2007-06-27 20:55 ` Quôc Peyrot
2007-06-27 20:58 ` Pal-Kristian Engstad
2007-06-27 21:18 ` Quôc Peyrot [this message]
2007-06-27 21:18 ` Pal-Kristian Engstad
2007-06-27 21:34 ` Quôc Peyrot
2007-06-27 22:13 ` Pal-Kristian Engstad
2007-06-27 15:18 ` [Caml-list] The Implicit Accumulator: a design pattern using optional arguments Jon Harrop
2007-06-27 16:44 ` Thomas Fischbacher
2007-06-27 18:17 ` Jon Harrop
2007-06-28 11:18 ` Thomas Fischbacher
2007-06-29 13:15 ` Bill Wood
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=C1E56D74-E1D0-4CC0-B1BE-3B7B67BBA0D2@lrde.epita.fr \
--to=chojin@lrde.epita.fr \
--cc=caml-list@yquem.inria.fr \
--cc=pal_engstad@naughtydog.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).