zbMATH — the first resource for mathematics

Hypothetical analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet. (English) Zbl 0747.68032
Summary: The first analysis of approximate counting is due to Ph. Flajolet [BIT 25, 113-134 (1985; Zbl 0562.68027)], whereas the first satisfactory analysis of the average path length in digital search trees has been performed by D. E. Knuth [The art of computer programming. Vol. 3: Sorting and searching. Reading: Addison-Wesley Publ. Comp. (1974; Zbl 0302.68010)]. Both authors have used the Mellin integral transform, but in rather different ways. It was shown by P. Kirschenhofer and H. Prodinger [RAIRO, Inf. Theor. Appl. 25(1), 43-48 (1991; Zbl 0732.68052)] that both problems are very similar. (This note contains also an “explanation” of this phenomenon.)
It is amusing to figure out what Flajolet and Knuth would have done by considering the exchanged problems. The aim of this note is to perform these analyses.

68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
05A15 Exact enumeration problems, generating functions
68W10 Parallel algorithms in computer science
Full Text: DOI
[1] Flajolet, P., Approximate counting: a detailed analysis, Bit, 25, 113-134, (1985) · Zbl 0562.68027
[2] Flajolet, P.; Vitter, J., Average-case analysis of algorithms and data structures, (), 431-524 · Zbl 0900.68251
[3] Kirschenhofer, P.; Prodinger, H., Approximate counting: an alternative approach, RAIRO theoretical informatics, 25, 43-48, (1991) · Zbl 0732.68052
[4] Knuth, D.E., The art of computer programming, Vol. 3, (1973), Addison-Wesley Reading, MA · Zbl 0191.17903
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.