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: 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
think?)

Regards,
Lars Nilsson

From: "Krishnaswami, Neel" <neelk@cswcasa.com>
> 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