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:

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:

https://arxiv.org/abs/1804.01823

You may be interested in the classic papers by Robert Tarjan and others:

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.