What is Amortized Analysis? And how can it help me achieve worst-case performance guarantees in my programs?
I was reading that the following techniques can help the programmer achieve Worst-case performance guarantees (i.e. in my own words: guarantee that the running time of a program would not exceed the running time in the worst cast):
- Randomized algorithms (e.g. quicksort algorithm is quadratic in worst case, but randomly ordering the input gives a probabilistic guarantee that its running time is linearithmic )
- Sequences of operations (our analysis must take into account both data and the sequence of operations performed by the client)
- Amortized Analysis (another way to provide a performance guarantee is to amortize the cost, by keeping track of the total cost of all operations, divided by the number of operations. In this setting, we can allow some expensive operations, while keeping the average cost of operations low. In other words, we spread the cost of the few expensive operations, by assigning a portion of it to each of a large number of inexpensive operations)
The author mentioned the use of resizing array data structure for Stack as one example of how to achieve amortized analysis but I still don't understand what amortized analysis is, and how it can actually be implemented (data structure? algorithm?) to achieve worst-cast performance guarantees