Analysis of tree algorithm for collision resolution
Résumé
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)$.
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...