<p>Amortized analysis is appropriate to analyse a <em>sequence</em> of operations. That is where your &quot;data structure&quot; bent comes into the picture. Your example of the analysis of the Euclidean algorithm is a case in point: You analyse the behaviour of a sequence of non-trivial operations on a very simple data structure (two elements).</p>
<p>In any case, Jeff Erickson (of <a href="https://jeffe.cs.illinois.edu/teaching/algorithms" rel="nofollow noreferrer">Algorithms</a> fame) said he hasn't used his amortized analysis notes for quite some time.</p>

CC BY-SA 4.0
2021-07-20T21:32:26.367Z
2021-07-20T21:32:26.367Z
vonbrand
<p><a href="https://en.wikipedia.org/wiki/Amortized_analysis" rel="nofollow noreferrer">Amortized analysis</a> is often taught in algorithms classes, with the different <em>methods</em> (aggregate, accounting, potential). It is <em>very important</em> when discussing some data structures and their use in algorithms since worst-case analysis is sometimes quite far from the actual behavior.</p>
<p>My question is: Where is an amortized analysis used, <strong>not</strong> related to data structures?</p>
<p>Two points to clarify what I mean by <em>not related to data structures</em>:</p>
<ol>
<li>Amortized analysis can be used to analyze <a href="https://en.wikipedia.org/wiki/Kruskal%27s_algorithm" rel="nofollow noreferrer">Kruskal's algorithm</a>, but it is very much related to data structure: the amortized aspect is related to the <em>union-find</em> data structure.</li>
<li>The <a href="https://en.wikipedia.org/wiki/Euclidean_algorithm" rel="nofollow noreferrer">Euclidean algorithm</a> to compute the gcd of two integers <span class="math-container">$a$</span> and <span class="math-container">$b$</span> can be analyzed through amortized analysis: though some step decreases <span class="math-container">$b$</span> only by one unit, it actually decreases by a constant factor <em>in average</em>. <em>Cf.</em> for instance <a href="http://www.lirmm.fr/%7Egrenet/publis/GV20.pdf" rel="nofollow noreferrer">this paper</a> (<em>caveat: I am one of the authors</em>) that uses a potential function or the analysis in Knuth's book. I consider that this is amortized analysis not related to the data structure.</li>
</ol>
<p>Of course, the border between <em>related to data structure</em> and <em>not related to data structure</em> is probably ill-defined. A more precise version of my question could then be: What are examples of amortized analysis of algorithms, that are least related to data structure?</p>

CC BY-SA 4.0
2021-08-26T15:01:43.067Z
Another classical example is "Can I optimize an operation that I will have to repeat `m` times on my collection of items, by first moving my `n` items into a well-suited data structure?" And then you need to compare the cost of building a data structure (which depends on n and will be higher for a complex structure) with the repeated cost of the operation (which is of the form `m * something(n)` where the something might be lower for a complex structure).
Stef
<algorithms>
Example of amortized analysis of algorithms rather than data structures
# Example of amortized analysis of algorithms rather than data structures

(Asked by: username_0 on 2021-07-11)

[Amortized analysis](https://en.wikipedia.org/wiki/Amortized_analysis) is often taught in algorithms classes, with the different *methods* (aggregate, accounting, potential). It is *very important* when discussing some data structures and their use in algorithms since worst-case analysis is sometimes quite far from the actual behavior.

My question is: Where is an amortized analysis used, **not** related to data structures?

Two points to clarify what I mean by *not related to data structures*:

1. Amortized analysis can be used to analyze [Kruskal's algorithm](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm), but it is very much related to data structure: the amortized aspect is related to the *union-find* data structure.
2. The [Euclidean algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm) to compute the gcd of two integers $a$ and $b$ can be analyzed through amortized analysis: though some step decreases $b$ only by one unit, it actually decreases by a constant factor *in average*. *Cf.* for instance [this paper](http://www.lirmm.fr/%7Egrenet/publis/GV20.pdf) (*caveat: I am one of the authors*) that uses a potential function or the analysis in Knuth's book. I consider that this is amortized analysis not related to the data structure.

Of course, the border between *related to data structure* and *not related to data structure* is probably ill-defined. A more precise version of my question could then be: What are examples of amortized analysis of algorithms, that are least related to data structure?

**Tags:** algorithms

> **Comments:**
> **username_1**: Another classical example is "Can I optimize an operation that I will have to repeat `m` times on my collection of items, by first moving my `n` items into a well-suited data structure?" And then you need to compare the cost of building a data structure (which depends on n and will be higher for a complex structure) with the repeated cost of the operation (which is of the form `m * something(n)` where the something might be lower for a complex structure).  

---

## 1 answers

### Answer by username_2 on 2021-07-20. Score: 1

Amortized analysis is appropriate to analyse a *sequence* of operations. That is where your "data structure" bent comes into the picture. Your example of the analysis of the Euclidean algorithm is a case in point: You analyse the behaviour of a sequence of non-trivial operations on a very simple data structure (two elements).

In any case, Jeff Erickson (of [Algorithms](https://jeffe.cs.illinois.edu/teaching/algorithms) fame) said he hasn't used his amortized analysis notes for quite some time.


---

