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 AAA13093; Fri, 24 Aug 2001 00:29:59 +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 AAA13204 for ; Fri, 24 Aug 2001 00:29:58 +0200 (MET DST) Received: from smtprelay3.adelphia.net (smtprelay3.adelphia.net [64.8.25.8]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f7NMTuH08171 for ; Fri, 24 Aug 2001 00:29:56 +0200 (MET DST) Received: from mordor ([24.48.116.108]) by smtprelay3.adelphia.net (Netscape Messaging Server 4.15) with SMTP id GIJL6O00.HAV for ; Thu, 23 Aug 2001 18:30:24 -0400 Message-ID: <002d01c12c23$2179ea40$0200a8c0@buf.adelphia.net> From: "Lars Nilsson" To: References: Subject: Re: [Caml-list] time complexity on basic data types Date: Thu, 23 Aug 2001 18:29:53 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4522.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk At the risk of making a fool of myself in public, is there such a thing as insertion in a list at all in Ocaml? From what I have seen there is only concatenation of a single element and a list (::), and operations would have to be defined with this by means recursion/iteration. If this is the case, I assume insertion at some point in a list would have O(n) complexity in the general case? If not, what am I missing (@ being something other than I think?) Regards, Lars Nilsson From: "Krishnaswami, Neel" > Collin Monahan [mailto:cmonahan@fame.com] wrote: > > > > With respect to arrays and lists, is the complexity for operations > > on these data structures like "normal?" E.g. random access in arrays > > in constant time, insertion in lists in constant time, random access > > in lists in linear time . . . > > Yep, that's correct. ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr