Upper tail analysis of bucket sort and random tries

DOI10.1016/j.tcs.2021.09.029OpenAlexW3199018719MaRDI QIDQ5925527

Guy Even, Ioana O. Bercea

Publication date: 18 November 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.10499

zbMATH Keywords

sortingrandomized algorithmsanalysis of running time

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the tails of the limiting Quicksort distribution
• On The variance of the extremal path length in a symmetric digital trie
• Analytic variations on bucket selection and sorting
• Tail bounds for sums of geometric and exponential variables
• Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm
• Dynamical sources in information theory: A general analysis of trie structures
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• A limiting distribution for quicksort
• Large Deviations for Quicksort
• New results on the size of tries
• Quicksort asymptotics
• Sequential and Parallel Algorithms and Data Structures
• Concentration of Measure for the Analysis of Randomized Algorithms
• Upper tail analysis of bucket sort and random tries

This page was built for publication: Upper tail analysis of bucket sort and random tries