More Web Proxy on the site http://driver.im/

research-article

Amortized Computational Complexity

Author:

Robert Endre TarjanAuthors Info & Claims

SIAM Journal on Algebraic Discrete Methods, Volume 6, Issue 2

Pages 306 - 318

https://doi.org/10.1137/0606031

Published: 01 April 1985 Publication History

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.

References

[1]

G. M. Adelson-Velskii, E. M. Landis, An algorithm for the organization of information, Soviet Math. Dokl., 3 (1962), 1259–1262

[2]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975x+470

[3]

Brian Allen, Ian Munro, Self-organizing binary search trees, J. Assoc. Comput. Mach., 25 (1978), 526–535

Digital Library

[4]

R. Bayer, Symmetric binary B-trees: data structure and maintenance algorithms, Acta Informat., 1 (1971/72), 290–306

Digital Library

[5]

R. Bayer, E. McCreight, Organization of large ordered indexes, Acta Inform., 1 (1972), 173–189

Digital Library

[6]

J. L. Bentley, C. McGeogh, Worst-case analysis of self-organising sequential search heuristics, Proc. 20th Allerton Conference on Communication, Control, and Computing, to appear

[7]

James R. Bitner, Heuristics that dynamically organize data structures, SIAM J. Comput., 8 (1979), 82–110

Digital Library

[8]

Mark R. Brown, Robert E. Tarjan, Design and analysis of a data structure for representing sorted lists, SIAM J. Comput., 9 (1980), 594–614

Digital Library

[9]

C. A. Crane, Linear lists and priority queues as balanced binary trees, Technical Report, STAN-CS-72-259, Computer Science Dept., Stanford University, Stanford, CA, 1972

[10]

Harold N. Gabow, Robert Endre Tarjan, A linear-time algorithm for a special case of disjoint set union, J. Comput. System Sci., 30 (1985), 209–221

[11]

B. A. Galler, M. J. Fischer, An improved equivalence algorithm, Comm. ACM, 7 (1964), 301–303

Digital Library

[12]

Leo J. Guibas, Edward M. McCreight, Michael F. Plass, Janet R. Roberts, A new representation for linear lists, Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977), Assoc. Comput. Mach., New York, 1977, 49–60

[13]

Leo J. Guibas, Robert Sedgewick, A dichromatic framework for balanced trees19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich., 1978), IEEE, Long Beach, Calif., 1978, 8–21

[14]

John Hopcroft, Robert Tarjan, Efficient planarity testing, J. Assoc. Comput. Mach., 21 (1974), 549–568

Digital Library

[15]

S. Huddleston, K. Mehlhorn, Robust balancing in B-trees, Proc. 5th GI-Conference on Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 104, Springer-Verlag, New York, 1981, 234–244

[16]

Scott Huddleston, Kurt Mehlhorn, A new data structure for representing sorted lists, Acta Inform., 17 (1982), 157–184

Digital Library

[17]

Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973xi+722 pp. (1 foldout), Sorting and Searching

[18]

Donald E. Knuth, James H. Morris, Jr., Vaughan R. Pratt, Fast pattern matching in strings, SIAM J. Comput., 6 (1977), 323–350

Digital Library

[19]

S. R. Kosaraju, Localized search in sorted lists, Proc. Thirteenth Annual ACM Symposium on Theory of Computing, 1978, 62–69

[20]

D. Maier, S. C. Salveter, Hysterical B-trees, Inform. Proc. Letters, 12 (1981), 199–202

[21]

J. Nievergelt, E. M. Reingold, Binary search trees of bounded balance, SIAM J. Comput., 2 (1973), 33–43

Digital Library

[22]

H. Olivie, A new class of balanced search trees: half-balanced binary search trees, RAIRO Inform. Théor., 16 (1982), 51–71

[23]

Ronald Rivest, On self-organizing sequential search heuristics, Comm. ACM, 19 (1976), 63–67

Digital Library

[24]

Pierre Rosenstiehl, Robert E. Tarjan, Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations, J. Algorithms, 5 (1984), 375–390

Digital Library

[25]

D. D. Sleator, R. E. Tarjan, Self-adjusting binary trees, Proc. Fifteenth Annual ACM Symposium on Theory of Computing, 1983, 235–245

[26]

Daniel D. Sleator, Robert E. Tarjan, Amortized efficiency of list update and paging rules, Comm. ACM, 28 (1985), 202–208

Digital Library

[27]

Daniel Dominic Sleator, Robert Endre Tarjan, Self-adjusting heaps, SIAM J. Comput., 15 (1986), 52–69

Digital Library

[28]

Daniel Dominic Sleator, Robert Endre Tarjan, Self-adjusting binary search trees, J. Assoc. Comput. Mach., 32 (1985), 652–686

Digital Library

[29]

Robert Endre Tarjan, Efficiency of a good but not linear set union algorithm, J. Assoc. Comput. Mach., 22 (1975), 215–225

Digital Library

[30]

Robert Endre Tarjan, A class of algorithms which require nonlinear time to maintain disjoint sets, J. Comput. System Sci., 18 (1979), 110–127

[31]

Robert Endre Tarjan, Updating a balanced search tree in $O(1)$ rotations, Inform. Process. Lett., 16 (1983), 253–257

[32]

R. E. Tarjan, Data Structures and Network Algorithms, CBMS Regional Conference Series in Applied Mathematics, Vol. 44, Society for Industrial and Applied Mathematics, Philadelphia, 1983

[33]

Robert E. Tarjan, Jan van Leeuwen, Worst-case analysis of set union algorithms, J. Assoc. Comput. Mach., 31 (1984), 245–281

Digital Library

[34]

, Webster's New World Dictionary of the American Language, World, Cleveland, Ohio, 1964, College Edition

Cited By

Pimpalkhare NKincaid Z(2024)Monotone Procedure Summarization via Vector Addition Systems and Inductive PotentialsProceedings of the ACM on Programming Languages10.1145/36897778:OOPSLA2(1873-1899)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689777
Haselwarter PLi Kde Medeiros MGregersen SAguirre ATassarotti JBirkedal L(2024)Tachis: Higher-Order Separation Logic with Credits for Expected CostsProceedings of the ACM on Programming Languages10.1145/36897538:OOPSLA2(1189-1218)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689753
Rajani VBarthe GGarg D(2024)A Modal Type Theory of Expected Cost in Higher-Order Probabilistic ProgramsProceedings of the ACM on Programming Languages10.1145/36897258:OOPSLA2(389-414)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689725
Show More Cited By

Index Terms

Amortized Computational Complexity

Index terms have been assigned to the content through auto-classification.

Recommendations

Amortized Communication Complexity

In this work we study the direct-sum problem with respect to communication complexity: Consider a relation $f$ defined over $\{0,1\}^{n} \times \{0,1\}^{n}$. Can the communication complexity of simultaneously computing $f$ on $\cal l$ instances $(x_1,...
Amortized communication complexity (Preliminary version)
SFCS '91: Proceedings of the 32nd annual symposium on Foundations of computer science

The authors study the direct sum problem with respect to communication complexity: Consider a function f: D to (0, 1), where D contained in (0, 1)/sup n/*(0, 1)/sup n/. The amortized communication complexity of f, i.e. the communication complexity of ...
Amortized complexity of data structures

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Algebraic and Discrete Methods

SIAM Journal on Algebraic and Discrete Methods Volume 6, Issue 2

Apr 1985

174 pages

ISSN:0196-5212

DOI:10.1137/sjamdu.1985.6.issue-2

Issue’s Table of Contents

Copyright © 1985 © Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 April 1985

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pimpalkhare NKincaid Z(2024)Monotone Procedure Summarization via Vector Addition Systems and Inductive PotentialsProceedings of the ACM on Programming Languages10.1145/36897778:OOPSLA2(1873-1899)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689777
Haselwarter PLi Kde Medeiros MGregersen SAguirre ATassarotti JBirkedal L(2024)Tachis: Higher-Order Separation Logic with Credits for Expected CostsProceedings of the ACM on Programming Languages10.1145/36897538:OOPSLA2(1189-1218)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689753
Rajani VBarthe GGarg D(2024)A Modal Type Theory of Expected Cost in Higher-Order Probabilistic ProgramsProceedings of the ACM on Programming Languages10.1145/36897258:OOPSLA2(389-414)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689725
Xia LIsrael LKramarz MColtharp NClaessen KWeirich SLi Y(2024)Story of Your Lazy Function’s Life: A Bidirectional Demand Semantics for Mechanized Cost Analysis of Lazy ProgramsProceedings of the ACM on Programming Languages10.1145/36746268:ICFP(30-63)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674626
Pham LSaad FHoffmann J(2024)Robust Resource Bounds with Static Analysis and Bayesian InferenceProceedings of the ACM on Programming Languages10.1145/36563808:PLDI(76-101)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656380
Pottier FGuéneau AJourdan JMével G(2024)Thunks and Debits in Separation Logic with Time CreditsProceedings of the ACM on Programming Languages10.1145/36328928:POPL(1482-1508)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632892
El Husseini WEl Vaigh CGoasdoué FJaudoin HChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Query Optimization for Ontology-Mediated Query AnsweringProceedings of the ACM Web Conference 202410.1145/3589334.3645567(2138-2148)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645567
Das AWang DHoffmann J(2023)Probabilistic Resource-Aware Session TypesProceedings of the ACM on Programming Languages10.1145/35712597:POPL(1925-1956)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571259
Sun HHuang XMa W(2023)Beyond Prediction: On-Street Parking Recommendation Using Heterogeneous Graph-Based List-Wise RankingIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.333680825:6(5892-5903)Online publication date: 11-Dec-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3336808
Chazelle BGuibas L(2023)Fractional cascading: I. A data structuring techniqueAlgorithmica10.1007/BF018404401:1-4(133-162)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840440
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents