Concepedia

Amortized Analysis Of Data Structures

Amortized Analysis of Data Structures is a formal analytical framework within the study of algorithms that characterizes the average time complexity of a sequence of operations on a data structure over time, distributing the cost of expensive operations across a series of cheaper ones to provide a more accurate long-term performance bound than worst-case analysis alone.

26

Publications

1.8K

Citations

41

Authors

24

Institutions

Publications per year

2017–2026

1

Parents

Publications

26

Amortized Computational Complexity

Robert E. Tarjan · SIAM Journal on Algebraic and Discrete Methods · 1985 · 525 citations

, , +16

Two algorithms for maintaining order in a list

Paul F. Dietz, Daniel D. Sleator · 1987 · 324 citations · Full text

, , +11

A PCP characterization of NP with optimal amortized query complexity

Alex Samorodnitsky, Luca Trevisan · 2000 · 174 citations

, , +12

Self-Adjusting Heaps

Daniel D. Sleator, Robert E. Tarjan · SIAM Journal on Computing · 1986 · 153 citations

, , +12

Amortized efficiency of a path retrieval data structure

Giuseppe F. Italiano · Theoretical Computer Science · 1986 · 112 citations

, , +14

1–5 of 26

Authors

41

  1. RE
    Robert E. Tarjan

    Princeton University, United States

    7 publications · 787 citations

    7

    h-index

  2. DD
    Daniel D. Sleator

    Carnegie Mellon University, United States

    4 publications · 523 citations

    4

    h-index

  3. GF
    Giuseppe F. Italiano

    University of Rome Tor Vergata, Italy

    2 publications · 203 citations

    2

    h-index

  4. LB
    Lam Berry Schoenmakers

    1 publications · 16 citations

    1

    h-index

  5. EP
    Erik Poll

    Radboud University Nijmegen, Netherlands

    1 publications · 16 citations

    1

    h-index

1–5 of 41

Institutions

24

  1. Sapienza University of Rome

    Rome, Italy

    2 h-index

    2 publications

    203 citations

  2. Carnegie Mellon University

    Pittsburgh, United States

    2 h-index

    2 publications

    342 citations

  3. Princeton University

    Princeton, United States

    2 h-index

    5 publications

    105 citations

  4. Schlumberger (United States)

    Houston, United States

    1 h-index

    1 publications

    324 citations

  5. Max Planck Institute for Informatics

    Saarbrücken, Germany

    1 h-index

    1 publications

    12 citations

  6. Stanford University

    Stanford, United States

    1 h-index

    3 publications

    63 citations

  7. Rutgers, The State University of New Jersey

    New Brunswick, United States

    1 h-index

    1 publications

    57 citations

  8. Radboud University Nijmegen

    Nijmegen, The Netherlands

    1 h-index

    1 publications

    16 citations

1–8 of 24

Venues

  1. SIAM Journal on Computing

    4 publications · 229 citations

    4

    h-index

  2. Journal of Functional Programming

    2 publications · 30 citations

    2

    h-index

  3. 1

    h-index

  4. Trends in Functional Programming

    Conference · 1 publications · 16 citations

    1

    h-index

  5. Algorithmica

    1 publications · 55 citations

    1

    h-index

1–5