Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-20T21:32:26.367Z
Answers.LastActivityDate: 2021-07-20T21:32:26.367Z
Answers.UserDisplayName: vonbrand
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-26T15:01:43.067Z
Comments.Text: 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).
Comments.UserDisplayName: Stef
Tags: <algorithms>
Title: Example of amortized analysis of algorithms rather than data structures
ThreadText: # 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.
  
  
  ---
  
  