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: 2001-08-23 (22:29)
From: Lars Nilsson <chamaeleon@a...>
Subject: Re: [Caml-list] time complexity on basic data types
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

Lars Nilsson

From: "Krishnaswami, Neel" <>
> Collin Monahan [] 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:  FAQ:
To unsubscribe, mail  Archives: