Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

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

You are right, only :: is possible. So insertion at arbitrary positions is O(n)

Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 45             
64293 Darmstadt     EMail:
Bug reports:  FAQ:
To unsubscribe, mail  Archives: