Version française
Home     About     Download     Resources     Contact us    
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: -- (:)
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, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners