DOCTORAL DISSERTATION DEFENSE
AMORTIZED COMPLEXITY OF DATA STRUCTURES
Candidate: Rajamani Sundar
Advisor: Ravi Boppana
Co-advisor: Richard Cole
2:30 p.m., Friday, May 3, 1991
room 101, Warren Weaver Hall
This thesis investigates the amortized complexity of
some fundamental data structure problems and
introduces interesting ideas
for proving lower bounds on amortized complexity
and for performing amortized analysis.
The problems are as follows:
- Dictionary Problem:
A dictionary is a dynamic set that supports searches of elements
and changes under insertions and deletions of elements.
It is open whether there exists a dictionary data structure
that takes constant amortized time per operation
and uses space polynomial in the
We prove that dictionary operations require log-logarithmic
amortized time under a multilevel hashing model
that is based on Yao's cell probe model.
- Splay Algorithm's Analysis:
Splay is a simple, efficient algorithm for searching
binary search trees, devised by Sleator and Tarjan,
that uses rotations to reorganize the tree.
Tarjan conjectured that
Splay takes linear time to process
deque operation sequences on a binary tree
and proved a special case of this conjecture called the
We prove tight bounds on the maximum numbers
of various types of right rotations in a
sequence of right rotations performed
on a binary tree. One of the lower bounds
refutes a conjecture of Sleator.
We apply the upper bounds to obtain
a nearly linear upper bound for Tarjan's conjecture.
We give two new proofs of the Scanning Theorem,
one of which is a potential-based proof
that solves a problem of Tarjan.
- Set Equality Problem:
The task of maintaining a dynamic collection of sets
under various operations
arises in many
We devise a fast data structure
for maintaining sets under equality-tests and
under creations of new sets through insertions and deletions of elements.
Equality-tests require constant time and
set-creations require logarithmic
This improves previous solutions.