I did a test, wanting to know the average time of the birthday paradox when searching collision into 2 tables (like the kangaroo problem).

The kangaroo method is announced to be 2.sqrt(n) but this is for a simple 2 stages algorithm where:
 - you first travel a single tame kangaroo sqrt(n) steps to setup a trap
 - then you make steps with the wild until a collision occurs (it falls in the trap), this second stage is expected to end in sqrt(n) steps.
The factor 2 comes from that. There no need of a hashtable there.


I did a test on 1.000.000 searches (24bits) using a table:

[ 999999] (2^12.825836) (Theoretical 2^12.825748)

It ends in sqrt(PI).sqrt(n) ~= 1.772.sqrt(n)

Note that the precision afer 1.000.000 test is about sqrt(1.000.000)=1000 so 3 digits are expected to be good.

2^0.825836 = 1.77256  , sqrt(PI) = 1.77245