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 CAA15287; Fri, 24 Aug 2001 02:26:41 +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 CAA15070 for ; Fri, 24 Aug 2001 02:26:40 +0200 (MET DST) Received: from moutvdom00.kundenserver.de (moutvdom00.kundenserver.de [195.20.224.149]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f7O0QdH09619 for ; Fri, 24 Aug 2001 02:26:39 +0200 (MET DST) Received: from [195.20.224.209] (helo=mrvdom02.schlund.de) by moutvdom00.kundenserver.de with esmtp (Exim 2.12 #2) id 15a4o2-0004Mw-00; Fri, 24 Aug 2001 02:26:38 +0200 Received: from drms-3e364b94.pool.mediaways.net ([62.54.75.148] helo=ice.gerd-stolpmann.de) by mrvdom02.schlund.de with esmtp (Exim 2.12 #2) id 15a4o2-00073J-00; Fri, 24 Aug 2001 02:26:38 +0200 Received: from localhost (localhost [[UNIX: localhost]]) by ice.gerd-stolpmann.de (8.9.3/8.9.3) id BAA14549; Fri, 24 Aug 2001 01:52:28 +0200 From: Gerd Stolpmann Reply-To: gerd@gerd-stolpmann.de Organization: privat To: "Lars Nilsson" , Subject: Re: [Caml-list] time complexity on basic data types Date: Fri, 24 Aug 2001 01:50:49 +0200 X-Mailer: KMail [version 1.0.28] Content-Type: text/plain References: <002d01c12c23$2179ea40$0200a8c0@buf.adelphia.net> In-Reply-To: <002d01c12c23$2179ea40$0200a8c0@buf.adelphia.net> MIME-Version: 1.0 Message-Id: <01082401522806.02716@ice> Content-Transfer-Encoding: 8bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 24 Aug 2001, Lars Nilsson wrote: >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?) You are right, only :: is possible. So insertion at arbitrary positions is O(n) time. Gerd -- ---------------------------------------------------------------------------- Gerd Stolpmann Telefon: +49 6151 997705 (privat) Viktoriastr. 45 64293 Darmstadt EMail: gerd@gerd-stolpmann.de Germany ---------------------------------------------------------------------------- ------------------- 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