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 LAA23642; Sat, 7 Dec 2002 11:28:25 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA23718 for ; Sat, 7 Dec 2002 11:28:25 +0100 (MET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id gB7ASFX17970; Sat, 7 Dec 2002 11:28:15 +0100 (MET) Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA23911; Sat, 7 Dec 2002 11:28:14 +0100 (MET) Date: Sat, 7 Dec 2002 11:28:14 +0100 From: Xavier Leroy To: Issac Trotts Cc: OCaml Mailing List Subject: Re: [Caml-list] function Message-ID: <20021207112814.A23052@pauillac.inria.fr> References: <20021203232211.GC22545@beech> <200212051000.LAA22469@pauillac.inria.fr> <20021205202448.GB524@boson.ucdavis.edu> <200212051800.55361.oleg_inconnu@myrealbox.com> <20021206213120.GC696@boson.ucdavis.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0i In-Reply-To: <20021206213120.GC696@boson.ucdavis.edu>; from ijtrotts@ucdavis.edu on Fri, Dec 06, 2002 at 01:31:21PM -0800 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > If the given list has L elements, each with S items, then flatten should > O((L*S)*L) = O(S*L^2) time, since you have to keep on churning through > every single element in the ever-expanding l at every recursive flatten > call. That's too bad. > Here's an experiment I tried: > [...] > I guess it looks linear because of the small input size. It's always a good idea to do experimental measurements to confirm a complexity analysis, just to make sure you haven't goofed. But when the measurements disagree with the analysis, you're supposed to go back to the analysis and find the flaw in it, not discard the experiment :-) More seriously: l1 @ l2 takes time O(length(l1)); the length of l2 doesn't matter since l2 isn't copied. This gives List.flatten a complexity of O(S*L) in your example (list of length L, each list element being of length S). This is optimal for immutable, singly-linked lists. - Xavier Leroy ------------------- 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