Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-08T11:27:24.986Z Has data issue: false hasContentIssue false
  • English
  • Français

On some applications of formulae of Ramanujan in the analysis of algorithms

Part of: Discrete mathematics in relation to computer science

Published online by Cambridge University Press:  26 February 2010

P. Kirschenhofer  and
H. Prodinger
P. Kirschenhofer
Affiliation:
Dr. P. Kirschenhofer, Institut für Algebra und Diskrete Mathematik, Technische Universität Wien, Wiedner Hauptstrasse 8-10, A-1040 Wien, Austria.
H. Prodinger
Affiliation:
Dr. H. Prodinger, Institut für Algebra und Diskrete Mathematik, Technische Universität Wien, Wiedner Hauptstrasse 8-10, A-1040 Wien, Austria.
Get access

Abstract

Using several transformation formulae from Ramanujan's second Notebook we achieve distribution results on random variables related to dynamic data structures (so-called “tries”). This continues research of Knuth, Flajolet and others via an approach that is completely new in this subject.

MSC classification

Secondary: 68R10: Graph theory (including graph drawing)
Type
Research Article
Information
Mathematika , Volume 38 , Issue 1 , June 1991 , pp. 14 - 33
Copyright
Copyright © University College London 1991

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Abramowitz, M. and Stegun, I. A.. Handbook of mathematical functions (Dover, New York, 1970).Google Scholar
2. Berndt, B. C.. Modular transformations and generalizations of several formulae of Ramanujan. Rocky Mountain J. Math, 7 (1977), 147–189.CrossRefGoogle Scholar
3. Delange, H.. Sur la fonction sommatoire de la fonction somme des chiffres. l'Enseignement Mathématique, 21 (1975), 31–47.Google Scholar
4. Flajolet, P.. Analyse d'algorithmes de manipulation d'arbres et de fichiers. Cahier de BURO, 34-35 (1981), 1–209.Google Scholar
5. Flajolet, P. and Ramshaw, L.. A note on Gray-Code and Odd-Even Merge. SIAMJ. Computing, 9 (1980), 142–158.CrossRefGoogle Scholar
6. Flajolet, P., Raoult, J.-C. and Vuillemin, J.. The number of registers required for evaluating arithmetic expressions. Theoret. Comp. Sci, 9 (1979), 99–125.CrossRefGoogle Scholar
7. Flajolet, P. and Sedgewick, R.. Digital search trees revisited. SIAM J. Comput., 15 (1986), 748–767.CrossRefGoogle Scholar
8. Hansen, E. R.. A table of series and products (Prentice-Hall, Englewood Cliffs, 1975).Google Scholar
9. Kirschenhofer, P., Prodinger, H. and Schoissengeier, J.. Zur Auswertung gewisser Reihen mit Hilfe modularer Funktionen, in: Zahlentheoretische Analysis 2, Hlawka, E., ed., Lecture Notes in Mathematics, 1262 (1987), 108–110.Google Scholar
10. Kirschenhofer, P., Prodinger, H. and Szpankowski, W.. On the variance of the external path length in a symmetric digital trie. Discrete Applied Math., 25 (1989), 129–143.Google Scholar
11. Knuth, D. E.. The art of computer programming, Vol. 3: “Sorting and searching” (Addison Wesley, Reading Mass, 1973).Google Scholar
12. Norlund, N. E.. Vorlesungen iiber Differenzenrechnung (Chelsea, New York, 1954).Google Scholar
13. Ramanujan, S.. Notebooks ofSrinivasa Ramanujan (2 volumes) (Tata Institute of Fundamental Research, Bombay 1957).Google Scholar
14. Schmid, U.. Analyse von Collision-Resolution Algorithmen in Random-Access Systemen mit dominanten Ubertragungskandlen (Dissertation, T. U. Wien, 1986).Google Scholar