Amortized Computational Complexity
Author:
- Robert Endre TarjanRTRobert Endre Tarjan
- 1 April 1985
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 6 (2) , 306-318
Abstract
A powerful technique in the complexity analysis of data structures is amortization, or averaging over time. Amortized running time is a realistic but robust complexity measure for which we can obtain surprisingly tight upper and lower bounds on a variety of algorithms. By following the principle of designing algorithms whose amortized complexity is low, we obtain “self-adjusting” data structures that are simple, flexible and efficient. This paper surveys recent work by several researchers on amortized complexity.Keywords
This publication has 28 references indexed in Scilit:
- A linear-time algorithm for a special case of disjoint set unionJournal of Computer and System Sciences, 1985
- A new data structure for representing sorted listsActa Informatica, 1982
- Design and Analysis of a Data Structure for Representing Sorted ListsSIAM Journal on Computing, 1980
- Heuristics That Dynamically Organize Data StructuresSIAM Journal on Computing, 1979
- Self-Organizing Binary Search TreesJournal of the ACM, 1978
- A dichromatic framework for balanced trees1978
- Efficient Planarity TestingJournal of the ACM, 1974
- Organization and maintenance of large ordered indexesActa Informatica, 1972
- Symmetric binary B-Trees: Data structure and maintenance algorithmsActa Informatica, 1972
- An improved equivalence algorithmCommunications of the ACM, 1964