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 SAA30417; Wed, 12 Nov 2003 18:18:33 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA29854 for ; Wed, 12 Nov 2003 18:18:31 +0100 (MET) Received: from hermes.jf.intel.com (fmr05.intel.com [134.134.136.6]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hACHIU123557 for ; Wed, 12 Nov 2003 18:18:30 +0100 (MET) Received: from petasus.jf.intel.com (petasus.jf.intel.com [10.7.209.6]) by hermes.jf.intel.com (8.12.9-20030918-01/8.12.9/d: outer.mc,v 1.66 2003/05/22 21:17:36 rfjohns1 Exp $) with ESMTP id hACHIfn0031175; Wed, 12 Nov 2003 17:18:41 GMT Received: from orsmsxvs040.jf.intel.com (orsmsxvs040.jf.intel.com [192.168.65.206]) by petasus.jf.intel.com (8.11.6-20030918-01/8.11.6/d: inner.mc,v 1.35 2003/05/22 21:18:01 rfjohns1 Exp $) with SMTP id hACHCG503767; Wed, 12 Nov 2003 17:12:20 GMT Received: from orsmsx331.amr.corp.intel.com ([192.168.65.56]) by orsmsxvs040.jf.intel.com (SAVSMTP 3.1.1.32) with SMTP id M2003111209180416313 ; Wed, 12 Nov 2003 09:18:04 -0800 Received: from orsmsx409.amr.corp.intel.com ([192.168.65.58]) by orsmsx331.amr.corp.intel.com with Microsoft SMTPSVC(5.0.2195.5329); Wed, 12 Nov 2003 09:18:04 -0800 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable X-MimeOLE: Produced By Microsoft Exchange V6.0.6487.1 Subject: RE: [Caml-list] Efficient and canonical set representation? Date: Wed, 12 Nov 2003 09:18:04 -0800 Message-ID: <3C4C3612EC443546A33E57003DB4F0F914C278@orsmsx409.jf.intel.com> Thread-Topic: [Caml-list] Efficient and canonical set representation? Thread-Index: AcOpORyrX9CDM3AlQpWYJ5xbhW3tYwAAM7hQ From: "Harrison, John R" To: "Diego Olivier Fernandez Pons" Cc: , "Harrison, John R" X-OriginalArrivalTime: 12 Nov 2003 17:18:04.0716 (UTC) FILETIME=[EEDFEEC0:01C3A940] X-Scanned-By: MIMEDefang 2.31 (www . roaringpenguin . com / mimedefang) X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 johnh:01 logarithmic:01 tree:02 canonical:03 somewhere:04 efficient:05 suspect:05 balanced:07 proven:91 insertion:08 john:09 john:09 interesting:09 comparisons:10 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk | It is not a coincidence. I remember having read somewhere that it | could be proven that if a balanced tree (based on comparisons) did not | have enough different representations of a same set, then the | insertion could not be done in logarithmic time. Interesting. I was beginning to suspect that might be the case. Does anyone have an exact reference for such a result? John. ------------------- 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