I am trying to get the amortized analysis for a complicated algorithm. I am wondering whether there are textbooks or illustrative examples that could serve as inspiration of techniques in amortized analysis.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Check out Jeff Erickson's notes on algorithms. jeffe.cs.illinois.edu/teaching/algorithms $\endgroup$– Chandra ChekuriCommented Sep 7, 2018 at 21:30
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
You may be interested in the classic papers by Robert Tarjan and others:
- "The Amortized Computational Complexity" by Robert Tarjan on a survey of amortized analysis of several algorithms and data structures.
- "Amortized Efficiency Of List Update and Paging Rules" by Daniel Sleator and Robert Tarjan on self-organizing lists.
- "Self-Adjusting Binary Search Trees" by Daniel Sleator and Robert Tarjan on splay trees.
- "Efficiency of a Good But Not Linear Set Union Algorithm" by Robert Tarjan on disjoint-set data structures.
- "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms" by Michael Fredman and Robert Tarjan on Fibonacci heaps.
The textbook CLRS: Introduction to Algorithms; 3rd edition also contains chapters on Fibonacci heaps (Chapter 19) and Disjoint-set data structures (Chapter 21).
I also find the lecture note "Amortized Analysis Explained" by Rebecca Fiebrink at Princeton University very helpful. It contains basic examples, in-depth examples, and some more involved examples.
$\begingroup$
$\endgroup$
For textbook references an interesting article is as follows:
https://www.geeksforgeeks.org/analysis-algorithm-set-5-amortized-analysis-introduction/
I can also refer to one recent paper which is very simple involving a straightforward application of amortized analysis:
