Version française
Home     About     Download     Resources     Contact us    
Browse thread
Re: [Caml-list] time complexity on basic data types
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Gerd Stolpmann <info@g...>
Subject: Re: [Caml-list] time complexity on basic data types
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