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 AAA14803; Fri, 6 Dec 2002 00:01:21 +0100 (MET) 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 AAA14411 for ; Fri, 6 Dec 2002 00:01:19 +0100 (MET) Received: from smtp-send.myrealbox.com (smtp-send.myrealbox.com [192.108.102.143]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id gB5N1I108651 for ; Fri, 6 Dec 2002 00:01:18 +0100 (MET) Received: from tw304h3 oleg_inconnu@smtp-send.myrealbox.com [156.111.84.180] by smtp-send.myrealbox.com with NetMail SMTP Agent $Revision: 3.20 $ on Novell NetWare via secured & encrypted transport (TLS); Thu, 05 Dec 2002 16:01:18 -0700 Content-Type: text/plain; charset="iso-8859-1" From: Oleg To: Issac Trotts , OCaml Mailing List Subject: Re: [Caml-list] function Date: Thu, 5 Dec 2002 18:00:55 -0500 User-Agent: KMail/1.4.3 References: <20021203232211.GC22545@beech> <200212051000.LAA22469@pauillac.inria.fr> <20021205202448.GB524@boson.ucdavis.edu> In-Reply-To: <20021205202448.GB524@boson.ucdavis.edu> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Message-Id: <200212051800.55361.oleg_inconnu@myrealbox.com> Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thursday 05 December 2002 03:24 pm, Issac Trotts wrote: > List.concat (List.map to_list2 strs);; ^^^^^^^^^ > > 2) What is the complexity of your function f ? > > The new ones have linear time complexity w.r.t. the number of > characters. The old one has quadratic time complexity. Issac I haven't analyzed your whole functions, but List.flatten'ing alone is=20 O(S*L^2), so while it may be linear WRT the number of characters in one=20 string, it's not necessarily linear WRT the total number of characters. S= ee=20 my version of f for O(L*S) time. Cheers Oleg ------------------- 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