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.