From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id FAA32350; Mon, 20 Sep 2004 05:56:23 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id FAA32377 for ; Mon, 20 Sep 2004 05:56:22 +0200 (MET DST) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i8K3uJFX004998 for ; Mon, 20 Sep 2004 05:56:21 +0200 Received: from [192.168.1.200] (ppp202-133.lns1.syd3.internode.on.net [203.122.202.133]) by smtp1.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i8K3uB4Y000294; Mon, 20 Sep 2004 13:26:11 +0930 (CST) Subject: Re: [Caml-list] Re: Set and Map question From: skaller Reply-To: skaller@users.sourceforge.net To: Seth Fogarty Cc: caml-list@pauillac.inria.fr In-Reply-To: References: Content-Type: text/plain Message-Id: <1095652570.2580.298.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 20 Sep 2004 13:56:10 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 414E54E3.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 sourceforge:01 2004:99 insertions:01 precalculate:01 9660:01 glebe:01 nsw:01 snail:02 tree:02 tree:02 checkout:02 2037:03 wrote:03 proportional:05 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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