Browse thread
[Caml-list] Set and Map question
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ 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, 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