Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise

DOI10.1007/978-3-540-85238-4_38zbMath1173.68458OpenAlexW1503775959MaRDI QIDQ3599150

Till Tantau, Bodo Manthey

Publication date: 3 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2007/1289/

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items (3)

On Smoothed Analysis of Quicksort and Hoare’s Find ⋮ On the Most Likely Voronoi Diagram and Nearest Neighbor Searching ⋮ Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise

Cites Work

• Unnamed Item
• Unnamed Item
• The analysis of Quicksort programs
• Smoothed analysis of binary search trees
• The height of a random binary search tree
• An analytic approach to the height of binary search trees II
• Smoothed analysis of algorithms
• Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
• Data Structures for Mobile Data
• Quicksort asymptotics
• Mathematical Foundations of Computer Science 2003
• Algorithms – ESA 2004
• Algorithms - ESA 2003

This page was built for publication: Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise