Amortized computational complexity. (English) Zbl 0599.68046

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.


68Q25 Analysis of algorithms and problem complexity
68P10 Searching and sorting
68-02 Research exposition (monographs, survey articles) pertaining to computer science
Full Text: DOI


[1] Adelson-Velskii, G. M.; Landis, E. M., An algorithm for the organization of information, Soviet Math. Dokl., 3, 1259, (1962)
[2] Aho, AlfredV.; Hopcroft, JohnE.; Ullman, JeffreyD., The design and analysis of computer algorithms, (1975) · Zbl 0326.68005
[3] Allen, Brian; Munro, Ian, Self-organizing binary search trees, J. Assoc. Comput. Mach., 25, 526, (1978) · Zbl 0388.68060
[4] Bayer, R., Symmetric binary B-trees: data structure and maintenance algorithms, Acta Informat., 1, 290, (197172) · Zbl 0233.68009
[5] Bayer, R.; McCreight, E., Organization of large ordered indexes, Acta Inform., 1, 173, (1972) · Zbl 0226.68008
[6] Worst-case analysis of self-organising sequential search heuristicsProc. 20th Allerton Conference on Communication, Control, and Computing, to appear
[7] Bitner, JamesR., Heuristics that dynamically organize data structures, SIAM J. Comput., 8, 82, (1979) · Zbl 0395.68022
[8] Brown, MarkR.; Tarjan, RobertE., Design and analysis of a data structure for representing sorted lists, SIAM J. Comput., 9, 594, (1980) · Zbl 0446.68047
[9] Linear lists and priority queues as balanced binary treesTechnical ReportSTAN-CS-72-259Computer Science Dept., Stanford UniversityStanford, CA1972
[10] Gabow, HaroldN.; Tarjan, RobertEndre, A linear-time algorithm for a special case of disjoint set union, J. Comput. System Sci., 30, 209, (1985) · Zbl 0572.68058
[11] Galler, B. A.; Fischer, M. J., An improved equivalence algorithm, Comm. ACM, 7, 301, (1964) · Zbl 0129.10302
[12] A new representation for linear listsConference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977)Assoc. Comput. Mach., New York19774960
[13] Guibas, LeoJ.; Sedgewick, Robert, A dichromatic framework for balanced trees, 19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich., 1978), 8, (1978), IEEE, Long Beach, Calif.
[14] Hopcroft, John; Tarjan, Robert, Efficient planarity testing, J. Assoc. Comput. Mach., 21, 549, (1974) · Zbl 0307.68025
[15] Robust balancing in B-treesProc. 5th GI-Conference on Theoretical Computer ScienceLecture Notes in Computer ScienceVol. 104Springer-VerlagNew York1981234244
[16] Huddleston, Scott; Mehlhorn, Kurt, A new data structure for representing sorted lists, Acta Inform., 17, 157, (1982) · Zbl 0481.68061
[17] Knuth, DonaldE., The art of computer programming. Volume 3, (1973) · Zbl 0302.68010
[18] Knuth, DonaldE.; Morris, Jr., JamesH.; Pratt, VaughanR., Fast pattern matching in strings, SIAM J. Comput., 6, 323, (1977) · Zbl 0372.68005
[19] Localized search in sorted listsProc. Thirteenth Annual ACM Symposium on Theory of Computing19786269
[20] Maier, D.; Salveter, S. C., Hysterical B-trees, Inform. Proc. Letters, 12, 199, (1981)
[21] Nievergelt, J.; Reingold, E. M., Binary search trees of bounded balance, SIAM J. Comput., 2, 33, (1973) · Zbl 0262.68012
[22] Olivie, H., A new class of balanced search trees: half-balanced binary search trees, RAIRO Inform. Théor., 16, 51, (1982) · Zbl 0489.68056
[23] Rivest, Ronald, On self-organizing sequential search heuristics, Comm. ACM, 19, 63, (1976) · Zbl 0317.68025
[24] Rosenstiehl, Pierre; Tarjan, RobertE., Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations, J. Algorithms, 5, 375, (1984) · Zbl 0588.68034
[25] Self-adjusting binary treesProc. Fifteenth Annual ACM Symposium on Theory of Computing1983235245
[26] Sleator, DanielD.; Tarjan, RobertE., Amortized efficiency of List update and paging rules, Comm. ACM, 28, 202, (1985)
[27] Sleator, DanielDominic; Tarjan, RobertEndre, Self-adjusting heaps, SIAM J. Comput., 15, 52, (1986) · Zbl 0618.68017
[28] Sleator, DanielDominic; Tarjan, RobertEndre, Self-adjusting binary search trees, J. Assoc. Comput. Mach., 32, 652, (1985) · Zbl 0631.68060
[29] Tarjan, RobertEndre, Efficiency of a good but not linear set union algorithm, J. Assoc. Comput. Mach., 22, 215, (1975) · Zbl 0307.68029
[30] Tarjan, RobertEndre, A class of algorithms which require nonlinear time to maintain disjoint sets, J. Comput. System Sci., 18, 110, (1979) · Zbl 0413.68039
[31] Tarjan, RobertEndre, Updating a balanced search tree in \(O(1)\) rotations, Inform. Process. Lett., 16, 253, (1983) · Zbl 0508.68041
[32] Tarjan, R. E., Data Structures and Network Algorithms, (1983) · Zbl 0584.68077
[33] Tarjan, RobertE.; van Leeuwen, Jan, Worst-case analysis of set union algorithms, J. Assoc. Comput. Mach., 31, 245, (1984) · Zbl 0632.68043
[34] Webster’s New World Dictionary of the American Language, (1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.