Amortized Computational Complexity
Robert Endre Tarjan · SIAM Journal on Algebraic and Discrete Methods · 1985
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.
Cited by 520 works. doi:10.1137/0606031
Authors
References
- The Design and Analysis of Computer Algorithms
- Fast Pattern Matching in Strings
- Data Structures and Network Algorithms
- Organization and maintenance of large ordered indexes
- Amortized efficiency of list update and paging rules
- Efficiency of a Good But Not Linear Set Union Algorithm
- Efficient Planarity Testing
- Self-adjusting binary search trees
- An improved equivalence algorithm
- A dichromatic framework for balanced trees