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 WAA09656; Wed, 10 Dec 2003 22:47:02 +0100 (MET) 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 WAA07354 for ; Wed, 10 Dec 2003 22:47:01 +0100 (MET) Received: from mailhost.ens-lyon.fr (pluvier.ens-lyon.fr [140.77.167.5]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hBALl0116288 for ; Wed, 10 Dec 2003 22:47:00 +0100 (MET) Received: by mailhost.ens-lyon.fr with scanned-ok (Exim 3.35 #1 (Debian)) id 1AUB53-0007sM-00 for ; Wed, 10 Dec 2003 21:37:09 +0100 Received: from mailhost.ens-lyon.fr ([127.0.0.1]) by localhost (pluvier [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 30258-01 for ; Wed, 10 Dec 2003 21:37:09 +0100 (CET) Received: from [140.77.128.119] (helo=ens-lyon.org) by mailhost.ens-lyon.fr with esmtp (Exim 3.35 #1 (Debian)) id 1AUB52-0007qy-00 for ; Wed, 10 Dec 2003 21:37:08 +0100 Message-ID: <3FD783F3.8020504@ens-lyon.org> Date: Wed, 10 Dec 2003 21:37:07 +0100 From: Jean-Baptiste Rouquier User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.5) Gecko/20031024 Debian/1.5-2 X-Accept-Language: en MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: [Caml-list] how to calculate a "xor" References: <20031205200829.7e29a2c6.Damien.Pous@ens-lyon.fr> In-Reply-To: <20031205200829.7e29a2c6.Damien.Pous@ens-lyon.fr> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: by amavisd-new-20030616-p5 (Debian) at ens-lyon.fr X-Loop: caml-list@inria.fr X-Spam: no; 0.00; ens-lyon:01 caml-list:01 damien:01 comparison:02 wrote:03 algorithm:03 algorithm:03 represented:07 lists:91 lists:91 consider:09 consider:09 something:09 something:09 think:11 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Damien wrote: > Hi algorithmers, > > Given two sets A and B, I want to calculate A\B _and_ B\A. > The sets are represented by lists. Consider the case A = [a_1; a_3; a_5; ...] and B = [a_2; a_4; a_6; ...] where a_i < a__{i+1}. I think it's a worst case for any algorithm. > without using an order to sort the lists, that is, if the only allowed comparison is "=" > is there something better than (...) (O(n2)) ? In my example, any algorithm has to test if a_{2i} = a_{2j+1}. So the worst case is O(n2). > with an order, is there something better than (O(n*ln n)) ? Consider the case where an algorithm M hasn't sorted B. So there are 2 consecutive elements, say a_4 and a_6, that hasn't been compared (directly or with transitivity). a_5 can't have been compared to both a_4 and a_6, let's consider a_5 hasn't been compared to a_4. Then M can't decide whether a_4 = a_5 or not, even using transitivity. This proove that any algorithm has to sort both A and B in my example, so the worst case is O(n ln n). See you soon, Jean-Baptiste. ------------------- 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