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 PAA14830; Mon, 15 Apr 2002 15:05:46 +0200 (MET DST) Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA14184 for caml-list@pauillac.inria.fr; Mon, 15 Apr 2002 15:05:45 +0200 (MET DST) 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 VAA08043 for ; Fri, 12 Apr 2002 21:47:34 +0200 (MET DST) Received: from laurelin.dementia.org ([208.167.88.73]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g3CJlWL25426 for ; Fri, 12 Apr 2002 21:47:32 +0200 (MET DST) Received: (from jprevost@localhost) by laurelin.dementia.org (8.11.6/8.11.6) id g3CJtxb97953; Fri, 12 Apr 2002 15:55:59 -0400 (EDT) (envelope-from visigoth@cs.cmu.edu) X-Authentication-Warning: laurelin.dementia.org: jprevost set sender to visigoth@cs.cmu.edu using -f To: Eric Merritt Cc: caml-list@inria.fr Subject: Re: [Caml-list] Simple question References: <20020412191529.79299.qmail@web13007.mail.yahoo.com> From: John Prevost Date: 12 Apr 2002 15:55:59 -0400 In-Reply-To: <20020412191529.79299.qmail@web13007.mail.yahoo.com> Message-ID: <86it6wlmi8.fsf@laurelin.dementia.org> User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.1 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk >>>>> "em" == Eric Merritt writes: em> by this I assume that the '@' function is not as strait em> forward as I thought it would be? In what manner does it em> append to the list to make the time 0(n^2)? -just curious. Actually, it's O(n) because it's straightforward and doesn't cause side-effects. The O(n^2) is when it is used n times. Here's an implementation that works similarly: let rec append a b = match (a,b) with | [], _ -> b | h::t, _ -> h :: append t b If you keep appending one element onto the end of a list, you can see that append has to run down the entire first list each time to build a new list with your new value at the end. If you append one item at the beginning each time, it behaves substatntially like :: does. So (@) is O(n) with n being the size of the first argument. John. ------------------- 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