Distribution of the size of random hash trees, pebbled hash trees and \(N\)-trees (Q5952094): Difference between revisions

The present mathematical note starts from the results of \textit{L. Devroye} [SIAM J. Comput. 28, No. 4, 1215--1224 (1999; Zbl 0939.68048)], that provide a computational analysis of the mean and size of random hash trees, pebbled hash trees, and \(N\)-trees. The aim of the article is to extend Devroye's results by deriving the limiting distribution of the (normed) size by using analytic techniques based on saddle-point approximations. The proposed approach has been successfully applied in hashing, and in bucket selection and sorting.