A general limit theorem for recursive algorithms and combinatorial structures

DOI10.1214/aoap/1075828056zbMath1041.60024MaRDI QIDQ1431560

Ludger Rüschendorf, Ralph Neininger

Publication date: 10 June 2004

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1075828056

zbMATH Keywords

contraction method; recursive structure; divide-and-conquer algorithm; multivariate limit law; Zolotarev metric

Mathematics Subject Classification ID

60F05: Central limit and other weak theorems

68P10: Searching and sorting

60F25: (L^p)-limit theorems

Related Items

On the total length of the random minimal directed spanning tree, On stochastic recursive equations of sum and max type, Distances in random digital search trees, The left-right-imbalance of binary search trees, The size of random fragmentation trees, On the contraction method with degenerate limit equation., Random binary trees: from the average case analysis to the asymptotics of distributions, Random environment on coloured trees, A functional limit theorem for the profile of search trees, Limiting theorems for the nodes in binary search trees, Limit distribution of distances in biased random tries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• Some average measures in m-ary search trees
• On the balance property of Patricia tries: External path length viewpoint
• Asymptotic expansions of the mergesort recurrences
• On the distribution of leaves in rooted subtrees of recursive trees
• A fixed point theorem for distributions
• On The variance of the extremal path length in a symmetric digital trie
• Mellin transforms and asymptotics. The mergesort recurrence
• Normal convergence problem? Two moments and a recurrence may be the clues
• The contraction method for recursive algorithms
• On the analysis of stochastic divide and conquer algorithms
• Phase changes in randomm-ary search trees and generalized quicksort
• On a multivariate contraction method for random recursive structures with applications to Quicksort
• Quickselect and the Dickman Function
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• Limit laws for local counters in random binary search trees
• Uniform Estimates of the Rate of Convergence in the Multi-Dimensional Central Limit Theorem
• Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees
• Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
• Ideal Metrics in the Problem of Approximating Distributions of Sums of Independent Random Variables
• Analysis of the space of search trees under the random insertion algorithm
• The Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and Power-of-2 Rules
• Digital Search Trees Again Revisited: The Internal Path Length Perspective
• The Joint Distribution of Elastic Buckets in Multiway Search Trees
• On the structure of random plane‐oriented recursive trees and their branches
• Total Path Length for Random Recursive Trees
• Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
• Rates of convergence for Quicksort
• A multivariate view of random bucket digital search trees
• An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
• An L₂ convergence theorem for random affine mappings
• Probability metrics and recursive algorithms
• Analysis of quickselect : an algorithm for order statistics
• Asymptotic distribution theory for Hoare's selection algorithm
• A limit theorem for “quicksort”
• Limit theorems for the number of maxima in random samples from planar regions