<p>You may be interested in the classic papers by  Robert Tarjan and others:</p>

<ul>
<li><a href="http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/Amortized.pdf" rel="nofollow noreferrer">"The Amortized Computational Complexity"</a> by Robert Tarjan on a survey of amortized analysis of several algorithms and data structures.</li>
<li><a href="https://www.cs.cmu.edu/~sleator/papers/amortized-efficiency.pdf" rel="nofollow noreferrer">"Amortized Efficiency Of List Update and Paging Rules"</a> by Daniel Sleator and Robert Tarjan on self-organizing lists.</li>
<li><a href="https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf" rel="nofollow noreferrer">"Self-Adjusting Binary Search Trees"</a> by Daniel Sleator and Robert Tarjan on splay trees.</li>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.437.8198&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">"Efficiency of a Good But Not Linear Set Union Algorithm"</a> by Robert Tarjan on disjoint-set data structures.</li>
<li><a href="http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Fibonacci-Heap-Tarjan.pdf" rel="nofollow noreferrer">"Fibonacci Heaps and Their Uses in Improved Network
Optimization Algorithms"</a> by Michael Fredman and Robert Tarjan on Fibonacci heaps.</li>
</ul>

<p>The textbook <a href="https://mitpress.mit.edu/books/introduction-algorithms-third-edition" rel="nofollow noreferrer">CLRS: Introduction to Algorithms; 3rd edition</a> also contains chapters on Fibonacci heaps (Chapter 19) and Disjoint-set data structures (Chapter 21).</p>

<p>I also find the lecture note <a href="https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf" rel="nofollow noreferrer">"Amortized Analysis Explained"</a> by Rebecca Fiebrink at Princeton University very helpful. It contains basic examples, in-depth examples, and some more involved examples.</p>

CC BY-SA 4.0
2018-10-08T13:05:41.303Z
2018-10-08T13:11:48.323Z
2018-10-08T13:11:48.323Z
hengxin
<p>For textbook references an interesting article is as follows:</p>

<p><a href="https://www.geeksforgeeks.org/analysis-algorithm-set-5-amortized-analysis-introduction/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/analysis-algorithm-set-5-amortized-analysis-introduction/</a></p>

<p>I can also refer to one recent paper which is very simple involving a straightforward application of amortized analysis:</p>

<p><a href="https://arxiv.org/abs/1804.01823" rel="nofollow noreferrer">https://arxiv.org/abs/1804.01823</a></p>

CC BY-SA 4.0
2018-09-07T09:21:20.077Z
2018-09-07T09:21:20.077Z
sbzk
<p>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.</p>

CC BY-SA 4.0
2018-09-07T21:30:50.733Z
Check out Jeff Erickson's notes on algorithms. http://jeffe.cs.illinois.edu/teaching/algorithms/
Chandra Chekuri
<reference-request><big-list><amortized-analysis>
Examples/Textbooks on amortized analysis of algorithms
shuhalo
# Examples/Textbooks on amortized analysis of algorithms

(Asked by: username_0 on 2018-09-06)

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.

**Tags:** reference-request, big-list, amortized-analysis
> **Comments:**
> **username_1**: Check out Jeff Erickson's notes on algorithms. http://jeffe.cs.illinois.edu/teaching/algorithms/  

---

## 2 answers

### Answer by username_2 on 2018-10-08. Score: 2

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

* ["The Amortized Computational Complexity"](http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/Amortized.pdf) by Robert Tarjan on a survey of amortized analysis of several algorithms and data structures.
* ["Amortized Efficiency Of List Update and Paging Rules"](https://www.cs.cmu.edu/~sleator/papers/amortized-efficiency.pdf) by Daniel Sleator and Robert Tarjan on self-organizing lists.
* ["Self-Adjusting Binary Search Trees"](https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf) by Daniel Sleator and Robert Tarjan on splay trees.
* ["Efficiency of a Good But Not Linear Set Union Algorithm"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.437.8198&rep=rep1&type=pdf) by Robert Tarjan on disjoint-set data structures.
* ["Fibonacci Heaps and Their Uses in Improved Network
  Optimization Algorithms"](http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Fibonacci-Heap-Tarjan.pdf) by Michael Fredman and Robert Tarjan on Fibonacci heaps.

The textbook [CLRS: Introduction to Algorithms; 3rd edition](https://mitpress.mit.edu/books/introduction-algorithms-third-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"](https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf) by Rebecca Fiebrink at Princeton University very helpful. It contains basic examples, in-depth examples, and some more involved examples.


---

### Answer by username_3 on 2018-09-07. Score: 1

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>


---

