Re: rate of finding collisions

[Ian Goldberg]

In article <[EMAIL PROTECTED]>,  <[EMAIL PROTECTED]> wrote:
>I wrote:
>>O(k*2^(N/2))?
>
>It has to be faster than that by a counting argument.  How much faster?

O(sqrt(k * 2^N)) = O(sqrt(k) * 2^(N/2))

The expected number of collisions you get if you sample S items out of
a universe of size U (=2^N in the above case) is about (S^2)/U.

   - Ian