scientific article; zbMATH DE number 7359755

DOI10.4230/LIPIcs.AofA.2018.23zbMath1478.68063MaRDI QIDQ4993545

Noela Müller, Henning Sulzbach, Michael Fuchs

Publication date: 15 June 2021

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

quadtreecentral limit theoremphase changecontraction methodstochastic fixed-point equationnumber of leavespositivity of variance

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Data structures (68P05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Phase changes in randomm-ary search trees and generalized quicksort
• Phase changes in random point quadtrees
• Limit laws for local counters in random binary search trees
• Analysis of the space of search trees under the random insertion algorithm
• The Joint Distribution of Elastic Buckets in Multiway Search Trees
• m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
• Hypergeometrics and the cost structure of quadtrees
• Refined quicksort asymptotics
• The CLT Analogue for Cyclic Urns
• A note on the quicksort asymptotics
• Dependence and phase changes in random m‐ary search trees