gen-briefly-explain-amortized-analysis-and-one-common-misconcept-17d5

Briefly explain amortized analysis and one common misconception about it.

# Amortized Analysis **Amortized analysis** is a technique for analyzing the average cost of operations in a data structure over a sequence of operations, rather than focusing on the worst-case cost of individual operations. ## Key Idea It distributes the cost of expensive operations across cheaper ones to show that the average cost per operation is small, even if some individual operations are costly. **Example:** Dynamic array resizing - Most insertions are O(1) - Occasionally we must resize (copy all elements) at O(n) - Amortized analysis shows each insertion averages to O(1) ## Common Misconception **"Amortized cost is the same as average-case complexity"** This is **wrong**. - **Average-case** depends on probability distributions of inputs - **Amortized cost** is a worst-case guarantee averaged over a sequence of operations—no probability involved Amortized analysis provides a worst-case bound on the average performance, making it stronger than typical average-case analysis.