On binary search tree recursions with monomials as toll functions

DOI10.1016/S0377-0427(01)00468-XzbMath1005.68115MaRDI QIDQ1612304

Ralph Neininger

Publication date: 22 August 2002

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

distributional recursions

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Searching and sorting (68P10) Characteristic functions; other transforms (60E10) Probability distributions: general theory (60E05) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (3)

Cost functionals for large (uniform and simply generated) random trees ⋮ Singularity analysis, Hadamard products, and tree recurrences ⋮ Limiting distributions for additive functionals on Catalan trees

Cites Work

• Unnamed Item
• Some asymptotic theory for the bootstrap
• A fixed point theorem for distributions
• Binary search tree recursions with harmonic toll functions
• The contraction method for recursive algorithms
• On the analysis of stochastic divide and conquer algorithms
• Sorting algorithms for broadcast communications: mathematical analysis.
• Some properties of a limiting distribution in Quicksort
• Universal Limit Laws for Depths in Random Trees
• On the internal path length ofd-dimensional quad trees
• Probability metrics and recursive algorithms
• A limit theorem for “quicksort”

This page was built for publication: On binary search tree recursions with monomials as toll functions