From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA06744; Fri, 30 Jul 2004 14:44:57 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA07632 for ; Fri, 30 Jul 2004 14:44:55 +0200 (MET DST) Received: from alex.baretta.com (h213-255-109-130.albacom.net [213.255.109.130] (may be forged)) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i6UCisEV001049 for ; Fri, 30 Jul 2004 14:44:54 +0200 Received: from baretta.com (localhost [127.0.0.1]) by alex.baretta.com (Postfix) with ESMTP id 199B82D5B90; Fri, 30 Jul 2004 08:45:59 -0400 (EDT) Message-ID: <410A4306.40609@baretta.com> Date: Fri, 30 Jul 2004 14:45:58 +0200 From: Alex Baretta User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.6) Gecko/20040113 X-Accept-Language: it, en-us, en MIME-Version: 1.0 To: Jon Harrop , Ocaml Subject: Re: [Caml-list] looping recursion References: <16646.64470.304530.264731@soggy.deldotd.com> <41097D53.5050607@baretta.com> <200407300136.14042.jon@jdh30.plus.com> In-Reply-To: <200407300136.14042.jon@jdh30.plus.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 410A42C6.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; baretta:01 baretta:01 caml-list:01 recursion:01 2004:99 unbounded:01 bounded:01 arrays:01 alex:01 alex:01 exists:01 exists:01 complexity:02 complexity:02 binary:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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