DMTCS Proceedings, 2005 International Conference on Analysis of Algorithms

Font Size:  Small  Medium  Large

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

Valid XHTML 1.0 Transitional