Hypothetical analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet.

*(English)*Zbl 0747.68032Summary: 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.

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.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68R05 | Combinatorics in computer science |

05A15 | Exact enumeration problems, generating functions |

68W10 | Parallel algorithms in computer science |

##### Keywords:

approximate counting; average path length in digital search trees; Mellin integral transform
PDF
BibTeX
XML
Cite

\textit{H. Prodinger}, Theor. Comput. Sci. 100, No. 1, 243--251 (1992; Zbl 0747.68032)

Full Text:
DOI

##### References:

[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.