On a multivariate contraction method for random recursive structures with applications to Quicksort
From MaRDI portal
Publication:2772929
DOI10.1002/rsa.10010zbMath0990.68054OpenAlexW2113913510MaRDI QIDQ2772929
Publication date: 19 February 2002
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.10010
Related Items (28)
Distribution of distances in random binary search trees. ⋮ One-sided variations on binary search trees ⋮ Bivariate issues in leader election algorithms with Marshall-Olkin limit distribution ⋮ Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme ⋮ Distances in random digital search trees ⋮ Inversions in split trees and conditional Galton--Watson trees ⋮ Higher moments of Banach space valued random variables ⋮ A limit process for partial match queries in random quadtrees and 2-d trees ⋮ On the size of paged recursive trees ⋮ Note on the exponential recursive k-ary trees ⋮ DEGREE PROFILE OF HIERARCHICAL LATTICE NETWORKS ⋮ Multi-dimensional smoothing transformations: existence, regularity and stability of fixed points ⋮ On densities for solutions to stochastic fixed point equations ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ On the Variety of Shapes on the Fringe of a Random Recursive Tree ⋮ Limiting theorems for the nodes in binary search trees ⋮ Dependence and phase changes in random m‐ary search trees ⋮ The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance ⋮ Asymptotic joint normality of counts of uncorrelated motifs in recursive trees ⋮ On weighted depths in random binary search trees ⋮ Limit laws for the Randić index of random binary tree models ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees ⋮ Partial match queries in random quadtrees ⋮ Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees ⋮ Limit distribution of distances in biased random tries ⋮ Random additions in urns of integers ⋮ On a functional contraction method ⋮ Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the joint distribution of the insertion path length and the number of comparisons in search trees
- Some asymptotic theory for the bootstrap
- A fixed point theorem for distributions
- Central and local limit theorems applied to asymptotic enumeration. IV: Multivariate generating functions
- The analysis of Quicksort programs
- On the invariance principle for sums of independent identically distributed random variables
- Analytic variations on quadtrees
- Central and local limit theorems applied to asymptotic enumeration. II: Multivariate generating functions
- Some properties of a limiting distribution in Quicksort
- An Analysis of Randomd-Dimensional Quad Trees
- A limiting distribution for quicksort
- Large Deviations for Quicksort
- Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees
- Combinatorial analysis of quicksort algorithm
- Universal Limit Laws for Depths in Random Trees
- On the internal path length ofd-dimensional quad trees
- The Joint Distribution of Elastic Buckets in Multiway Search Trees
- On the structure of random plane‐oriented recursive trees and their branches
- Hypergeometrics and the cost structure of quadtrees
- Increasing the efficiency of quicksort
- On the probability distribution of the values of binary trees
- A limit theorem for “quicksort”
- Convergence of two-dimensional branching recursions
This page was built for publication: On a multivariate contraction method for random recursive structures with applications to Quicksort
