Consider a problem involving updates and queries of a data structure.
Assume that there exists a family of algorithms which exhibit a
tradeoff between query and update time. We demonstrate a general
technique of constructing from such a family
a single algorithm with best amortized time. We indicate some applications
of this technique.
On the other hand, when a given algorithm achieves similar
amortized performance, we may be able to obtain from it a family
of algorithms that exhibit the underlying tradeoff. We exemplify this by
a family of union-find algorithms trading union time for find time.
The algorithms are obtained in a simple way from the well known path
compression algorithm.
A remark made in the paper regarding the complexity of union-find
is corrected.
