Analysis of tree algorithm for collision resolution
László Györfi, Sándor Győri
Abstract
For the tree algorithm introduced by [Cap79] and [TsMi78] let LN denote the expected collision resolution time given the collision multiplicity N. If L(z) stands for the Poisson transform of LN, then we show that LN - L(N) ≃ 1.29·10-4 cos(2 π log2 N + 0.698).
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page