Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Computational Complexity - Research Seminar

Stefan Schuh: Smoothed Bounds for the Height of Binary Search Trees Using Perturbed Indices

July 1, 2008, 10:15 a.m.
E 1 3, Room 415

Binary search trees are closely related to the running-time of the quicksort algorithm. Manthey and Tantau investigated the smoothed height of binary search trees with additive noise on the data to be inserted in the search tree. What happens if not the data itself, but the indices are perturbed? We are going to present a lower bound, which we suppose is tight, and an upper bound, which is to be refined later.