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:
- Amortized analysis can be used to analyze Kruskal's algorithm, but it is very much related to data structure: the amortized aspect is related to the union-find data structure.
- The 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 (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?
m
times on my collection of items, by first moving myn
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 formm * something(n)
where the something might be lower for a complex structure). $\endgroup$