Version française
Home     About     Download     Resources     Contact us    

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

Browse thread
[Caml-list] Set and Map question
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-09-20 (03:56)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Re: Set and Map question
On Mon, 2004-09-20 at 13:14, Seth Fogarty wrote:

> What I MEANT to ask is: Is there a O(n) method of set/map construction
> from a list, as opposed to the O(n log n) fold method.

It seems to me that in general that is impossible,
since random tree insertions are at least O(log n)
in the tree size (proportional to depth).

Perhaps you meant, assuming the list is sorted?
In that case, in theory you could precalculate
the shape of the tree just from the size, and then
fill in the elements in O(n).

John Skaller,
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: