4
$\begingroup$

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, but it is very much related to data structure: the amortized aspect is related to the union-find data structure.
  2. 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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$
    – Stef
    Aug 26, 2021 at 15:01

1 Answer 1

Reset to default
1
$\begingroup$

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 fame) said he hasn't used his amortized analysis notes for quite some time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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