Analysis of tree algorithm for collision resolution
László Györfi, Sándor Gyó́ri · Discrete Mathematics & Theoretical Computer Science · 2005
For the tree algorithm introduced by [Cap79] and [TsMi78] let $L_N$ denote the expected collision resolution time given the collision multiplicity $N$. If $L(z)$ stands for the Poisson transform of $L_N$, then we show that $L_N - L(N) ≃ 1.29·10^-4 \cos (2 π \log _2 N + 0.698)$.