Premium
On some applications of formulae of Ramanujan in the analysis of algorithms
Author(s) -
Kirschenhofer P.,
Prodinger H.
Publication year - 1991
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/s0025579300006409
Subject(s) - ramanujan's sum , mathematics , transformation (genetics) , distribution (mathematics) , subject (documents) , algorithm , combinatorics , computer science , mathematical analysis , library science , biochemistry , chemistry , gene
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.