This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] how to calculate a "xor"
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-12-10 (21:47) From: Jean-Baptiste Rouquier Subject: Re: [Caml-list] 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,
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

```