Basic Birthday Paradox question

[Sarad AV]

Hi,

I have a basic doubt of the birthday problem  for the case k=2, i.e 2 lists, where it is required to find a xor b =0(implies a=b; such that a is from the first list and b is from the second list).

Now, if we operate on 'n' bit values, then the basic algorithm is said to work in O( 2^(n/2) ) time and space. That is the time  and space requirement to find a collision between the two list.

What we do is fill the two lists(each) with  2^(n/2) random integers and 'JOIN' them. JOIN gives the elements that are common to both the lists.

JOIN (done efficiently) basically means sorting the two lists individually and then looking for a match between the two lists. We are assuming that we will have practical memory constrains when 'n' is large.

Sorting x elements can be done in O(x.log x) <--(1)


For e.g. 
if k=2 and x=256 elements; sorting takes O(x.log x) . 

But we store only 2^(n/2) elements in each list. Hence n=8 bits.
SO, we have 2^4 = 16 elements in each list. By eq (1), sorting takes
O(2^4 * 4) time= O(2^6) time.

Since x=256 , n=8 and we should have got O( 2^(n/2) ); i.e. O( 2^(8/2) ) =  O( 2^4 )  time complexity

there is a mismatch between the time complexities. what am I doing wrong here?

Thanks,
Sarad.