Amortized analysis

Question

In the Amortized analysis.

Average case running time: average over all possible inputs for one algorithm (operation). If using probability, called expected running time

What is the different between expected time and Amortized time?

see: http://stackoverflow.com/questions/7333376/difference-between-average-case-and-amortized-analysis?rq=1 — sraok, Oct 29 '13 at 05:57

score 0 · Answer 1 · answered Oct 29 '13 at 08:27

Expected time:

We make some assumptions and, based on these assumptions, we make statements about the running time.

Hash tables is one such example. We assume that the data is well-distributed, and claim that the running time of operations are O(1), whereas the worst-case running time for an operation is actually O(n).

Amortized time:

Even though one operation may take longer than some given time, the time across multiple operations will balance out to give the mentioned running time.

(Well-implemented) self-resizing arrays is one such example. When you insert, it takes O(n) to resize the array, but, across many inserts, each will take O(1) on average.

Amortized analysis

1 Answers1