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 NAA15894; Sat, 13 Apr 2002 13:10:56 +0200 (MET DST) 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 NAA16222 for ; Sat, 13 Apr 2002 13:10:55 +0200 (MET DST) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from mel-rto4.wanadoo.fr (smtp-out-4.wanadoo.fr [193.252.19.23]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g3DBAsL09980 for ; Sat, 13 Apr 2002 13:10:54 +0200 (MET DST) Received: from mel-rta4.wanadoo.fr (193.252.19.58) by mel-rto4.wanadoo.fr; 13 Apr 2002 13:10:54 +0200 Received: from debian (80.8.75.187) by mel-rta4.wanadoo.fr; 13 Apr 2002 13:10:23 +0200 Received: from moi by debian with local (Exim 3.35 #1 (Debian)) id 16wLQI-0000fY-00 for ; Sat, 13 Apr 2002 13:10:26 +0200 To: caml-list@inria.fr Subject: Re: [Caml-list] Simple question References: <20020412191529.79299.qmail@web13007.mail.yahoo.com> From: Remi VANICAT Date: 13 Apr 2002 13:10:26 +0200 In-Reply-To: <20020412191529.79299.qmail@web13007.mail.yahoo.com> Message-ID: <87sn5zg8gt.dlv@wanadoo.fr> User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-15 Content-Transfer-Encoding: 8bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Eric Merritt writes: > > erg, apply_fun_list become tail recursive, but it's > > in O(n^2) (when > > the first version is in O(n)), and as @ is not tail > > recursive, this > > doesn't resolve the problem of Usage of the > > stack.... > > > > better stick to the non tail recursive version that > > to do this. > > by this I assume that the '@' function is not as > strait forward as I thought it would be? In what > manner does it append to the list to make the time > 0(n^2)? -just curious. so let's look at : let rec apply_fun_list x f_list accum = match f_list with h::t -> apply_fun_list x t (accum@(h x)) | [] -> accum;; so the line "apply_fun_list x t (accum@(h x))" is done O(n) time (one time for each element in f_list), and "(accum@(h x))" take time O(n), so the time taken by this algorithm is O(n)*O(n)=O(n^2). -- Rémi Vanicat vanicat@labri.u-bordeaux.fr http://dept-info.labri.u-bordeaux.fr/~vanicat ------------------- 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