Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] looping recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Alex Baretta <alex@b...>
Subject: Re: [Caml-list] looping recursion
Jon Harrop wrote:
> On Thursday 29 July 2004 23:42, you wrote:
> 
>>...I won't by
>>imperative programming for anything at all...
> 
> 
> What would you do if you wanted a data structure with O(1) lookup?

Such structures do not exists. Remember that complexity theory deals 
with *unbounded* input sizes. As you can well imagine, there exists no 
such thing as an indefinitely large datastructure with O(1) time 
complexity. Arrays are O(1) only if you preallocate them to the maximum 
size allowed by the application. But, in this case, even a binary search 
in Map.t is O(1): that is, bounded by a constant.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners