Abstract
In this paper we perform an amortized analysis of a functional program for splaying. We construct a potential function that yields the same bound for the amortized cost of splaying as given by D.D. Sleator and R.E. Tarjan - the inventors of splay trees. In addition, we show that this bound is minimal for the class of "sum of logs" potentials. Our approach also applies to the analysis of path reversal and pairing heaps.
Original language | English |
---|---|
Pages (from-to) | 41-50 |
Journal | Information Processing Letters |
Volume | 45 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1993 |