(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)
An improved worst-case bound on the dictionary problem
in a comparison-based model of computation is presented.
Dictionary operation can be performed at a
worst-case cost of
O(log n), using only
ceiling(log (n + 1) epsilon)
comparisons, where epsilon
is an arbitrary positive constant.
We feel that this fact leads to a deeper understanding of
of this well-studied and fundamental problem.
We also give two applications.
First, we improve the upper bound on on-line sorting:
for each value of delta, delta > 0,
there is a worst-case efficient on-line sorting algorithm using less than
sum_{n=1 to N} ceiling (log n) + delta N + log N
comparisons when sorting N elements.
By worst-case efficient on-line we mean that the worst-case cost of adding an
element is Theta(log n), n is the number of elements added so far.
Second,
we show how to maintain a binary search tree with
an optimal height of exactly ceiling(log(n+1)) at an
amortized cost of
log^2 n per insertion.