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.
For textbook references an interesting article is as follows:
I can also refer to one recent paper which is very simple involving a straightforward application of amortized analysis:
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.