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.
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.
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: