Amortized Analysis

Amortized Analysis is a method in algorithm analysis that characterizes the average time complexity of a sequence of operations by attributing to each operation a cost that reflects the total workload spread over the sequence, rather than the maximum cost of any single operation.

127

Publications

8.4K

Citations

227

Authors

124

Institutions

Publications per year

2017–2026

Parents

Algorithms

Children

Amortized ComplexityAmortized CostAmortized Lower BoundsAmortized Running TimeBinary Counter AnalysisBinomial Heap AnalysisBit Reversal Permutation AnalysisDeamortizationDijkstra’s Algorithm AnalysisDisjoint Set Union Analysis

Publications

127

Amortized efficiency of list update and paging rules

Daniel D. Sleator, Robert E. Tarjan · Communications of the ACM · 1985 · 2.1K citations · Full text

Computing, Computer Engineering, Computer Science +17

On the Average Number of Maxima in a Set of Vectors and Applications

Jon Bentley, H. T. Kung, Mario Schkolnick et al. · Journal of the ACM · 1978 · 372 citations · Full text

Computing, Computer Science, Algorithms +4

Two algorithms for maintaining order in a list

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

Computing, Computer Science, Algorithms +11

Key Management for Large Dynamic Groups: One-Way Function Trees and Amortized Initialization

David Balenson, David McGrew, Alan T. Sherman · 2000 · 240 citations

Computing, Computer Science, Computer Systems +14

A TABLE FOR THE CALCULATION OF WORKING PROBITS AND WEIGHTS IN PROBIT ANALYSIS

D. J. Finney, Wallace Stevens · Biometrika · 1948 · 224 citations

Social Sciences, Biostatistics, Economics +6

1–5 of 127

Authors

227

JH
Jan Hoffmann
Carnegie Mellon University, United States
15 publications · 828 citations
14
h-index
RE
Robert E. Tarjan
Princeton University, United States
12 publications · 2.5K citations
12
h-index
DD
Daniel D. Sleator
Carnegie Mellon University, United States
7 publications · 2.6K citations
7
h-index
SJ
Steffen Jost
Ludwig-Maximilians-Universität München, Germany
5 publications · 196 citations
5
h-index
MH
Martin Hofmann
Ludwig-Maximilians-Universität München, Germany
4 publications · 379 citations
4
h-index

1–5 of 227

Institutions

124

1–8 of 124

Venues

SIAM Journal on Computing
7 publications · 373 citations
7
h-index
Journal of the ACM
JACM · 5 publications · 545 citations
5
h-index
ACM SIGPLAN Notices
5 publications · 168 citations
5
h-index
arXiv (Cornell University)
Repository · 4 publications · 166 citations
4
h-index
Communications of the ACM
3 publications · 2.3K citations
3
h-index

1–5