[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20031210 (21:47) 
From:  JeanBaptiste Rouquier <jeanbaptiste.rouquier@e...> 
Subject:  Re: [Camllist] how to calculate a "xor" 
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, JeanBaptiste.  To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners