Re: efficient compare

From: Andersen <andersen_800_at_hotmail.com>
Date: Thu, 27 Apr 2006 21:44:12 +0200
Message-ID: <44511F0C.60804_at_hotmail.com>

Jan Hidders wrote:
> Andersen wrote:

>> Rephrasing it in math terminology:
>> If I have two sets A, and B, containing tuples, and I want to find
>> complement(A intersect B), how do I do that efficiently?

>
> Just as a small side note: since the worst-case communication
> complexity of comparing two strings is O(n) where n is the length of
> the strings you won't be able to do better than that in the worst case.

Of course, but that is a worst case analysis. Roughly speaking (not exactly the same problem), I want to compare two strings and make one into the other (similar to RSYNC), but having to transfer as little as possible over the network. Received on Thu Apr 27 2006 - 21:44:12 CEST