Upper tail analysis of bucket sort and random tries

DOI10.1016/J.TCS.2021.09.029MaRDI QIDQ5925527zbMATH OpenOpenAlexFDO

Authors Ioana O. Bercea, Guy Even

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

analysis of running timerandomized algorithmssorting

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Upper tail analysis of bucket sort and random tries
• A probabilistic analysis of the height of tries and of the complexity of triesort
• Analytic variations on bucket selection and sorting
• On the tails of the limiting Quicksort distribution
• Stochastic analysis of Shell Sort
• Asymptotic estimates for the higher moments of the expected behavior of straight insertion sort
• A randomized approximation algorithm for computing bucket orders
• On the tails of the limiting QuickSort density
• On the tails of the limiting QuickSort density

Cites work

• A limiting distribution for quicksort
• Analytic variations on bucket selection and sorting
• Concentration of Measure for the Analysis of Randomized Algorithms
• Data-specific analysis of string sorting
• Dynamical sources in information theory: A general analysis of trie structures
• scientific article; zbMATH DE number 5596834 (Why is no real title available?)
• scientific article; zbMATH DE number 4051016 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1142298 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• Introduction to algorithms.
• Large Deviations for Quicksort
• New results on the size of tries
• On the tails of the limiting Quicksort distribution
• On The variance of the extremal path length in a symmetric digital trie
• Optimal static and self-adjusting parameter choices for the (1+( , )) genetic algorithm
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Quicksort asymptotics
• Sequential and parallel algorithms and data structures. The basic toolbox
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Tail bounds for sums of geometric and exponential variables
• Upper tail analysis of bucket sort and random tries

Cited in

(2)

• Analytic variations on bucket selection and sorting
• Upper tail analysis of bucket sort and random tries

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5925527)