Werner Schachinger: Concentration of Distribution Results for Trie-Based Sorting of Continued Fractions

One method, studied in [FV98,CFV98], to sort $N$ real numbers is to store these numbers in a trie, based on comparing continuants of the corresponding continued fraction representations. In [CFV98] asymptotics of expected size and expected path length of these CF-trees have been derived in the setting, where the $N$ numbers are random variables independently drawn from an analytic density on the unit interval. We show that in that setting size and path length are tightly concentrated around their expected values, and also address the problem of finding limiting distributions.

Bibliography

CFV98

Julien Clément, Philippe Flajolet, and Brigitte Vallée.
The analysis of hybrid trie structures.
In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1998), pages 531-539, New York, 1998. ACM.

FV98

Philippe Flajolet and Brigitte Vallée.
Continued fraction algorithms, functional operators, and structure constants.
Theoret. Comput. Sci., 194(1-2):1-34, 1998.

Back to the Index