What is amortized analysis of algorithms?

algorithm analysis amortized-analysis
GrowinMan picture GrowinMan · Jun 19, 2012 · Viewed 49.8k times · Source

How is it different from asymptotic analysis? When do you use it, and why?

I've read some articles that seem to have been written well, like these:

but I've still not understood fully these concepts.

So, can anyone please simplify it for me?

Answer

harold picture harold · Jun 19, 2012

Amortized analysis doesn't naively multiply the number of invocations with the worst case for one invocation.

For example, for a dynamic array that doubles in size when needed, normal asymptotic analysis would only conclude that adding an item to it costs O(n), because it might need to grow and copy all elements to the new array. Amortized analysis takes into account that in order to have to grow, n/2 items must have been added without causing a grow since the previous grow, so adding an item really only takes O(1) (the cost of O(n) is amortized over n/2 actions).

Amortized analysis is not the same as an "average performance" - amortized analysis gives a hard guarantee on what the performance will do if you do so much actions.

Related questions

2^n complexity algorithm

I need to implement and test an algorithm with a 2^n complexity. I have been trying to find one for a while. If there is any way I can acheive this by implementation -- with a exact complexity of 2^n …

Read More
Reccurrence T(n) = T(n^(1/2)) + 1

I've been looking at this reccurrence and wanted to check if I was taking the right approach. T(n) = T(n^(1/2)) + 1 = T(n^(1/4)) + 1 + 1 = T(n^(1/8)) + 1 + 1 + 1 ... = 1 + 1 + 1 + ... + 1 (a total of rad n times) = n^(1/2) So the answer would come to theta bound …

Read More
What are a posteriori and a priori analyses of algorithm operations?

I am a new developer. Please help me understand what a posteriori and a priori analyses of algorithm operations are. I googled it, but I did not get any proper answers.

Read More