This Repository contains topics related to Amortized Analysis.
Amortized analysis is like budgeting for algorithms. Instead of focusing on the worst-case scenario for each operation, it looks at the overall cost of a sequence of operations. Imagine you have a data structure where some operations are more expensive than others. In amortized analysis, you distribute the total cost of all operations over each operation, providing a more balanced and realistic view of the average cost. It helps in understanding the average performance over time, even if individual operations may be costly.
Amortized analysis can be broadly classified into three types:
This type of analysis calculates the average cost per operation over a sequence of operations. You sum up the total cost of all operations and then divide it by the number of operations. This gives you an average cost.
In this method, you assign different "credits" or "charges" to different operations. The idea is to ensure that the total credits always cover the total cost, providing a more balanced view of the overall performance.
This approach defines a potential function that represents the accumulated "potential" energy of the data structure. The potential decreases with costly operations and increases when cheap operations are performed. The actual cost of an operation plus the change in potential gives the amortized cost.
| Lectures | Video Link | Video PDF |
|---|---|---|
| 1) Aggregate Analysis for Stack Operation |  |
 |
| 2) Incrementing binary number using Aggregate Analysis | |
|
| 3) Dynamic Table Using Aggregate Analysis | |
|
| 4) Stack operation using accounting method | |
|
| 5) Incrementing binary number using Accounting Analysis | |
|
| 6) Stack operation using potential method | |
|
| 7) Incrementing binary number using potential method | |
|
