Q4Design and Analysis of Algorithms

Amortized Analysis is a technique for analyzing the time complexity of an algorithm by averaging the worst-case cost over a sequence of n operations. It provides a more realistic average cost per operation even when occasional operations are expensive.

Three methods: (1) Aggregate Method — total cost of n operations divided by n; (2) Accounting Method — assign amortized costs, some prepay for future expensive operations; (3) Potential Method — use a potential function to measure stored energy. Example: Dynamic array doubling — individual push may cost O(n) when resizing, but amortized over all n pushes, each push costs O(1) amortized.