What is amortized analysis of algorithms?
algorithm, amortized-analysis, analysis
Solution
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.
Problem
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: http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf but I've still not fully understood these concepts. So, can anyone please simplify it for me?