gen-define-amortized-analysis-and-give-one-short-worked-example-320a

Define amortized analysis and give one short worked example.

# Amortized Analysis **Amortized analysis** is a technique for analyzing the average cost of operations in a sequence, even when individual operations may have varying costs. Instead of focusing on worst-case cost per operation, it determines the average cost per operation over a worst-case sequence of operations. ## Short Worked Example: Dynamic Array Append Consider a dynamic array that doubles in size when full: **Operation costs:** - Regular append: 1 unit - Append when full: n units (copy all elements to new array) **Sequence:** Start with size 1, append n items | Append # | Array Size | Cost | Running Total | |----------|------------|------|---------------| | 1 | 1 | 1 | 1 | | 2 | 2→4 | 2 | 3 | | 3 | 4 | 1 | 4 | | 4 | 4→8 | 4 | 8 | | 5-8 | 8 | 1 each | 12 | | 9 | 8→16 | 8 | 20 | **Total cost for n operations:** n + (1 + 2 + 4 + 8 + ... + n/2) = n + (n-1) ≈ 2n **Amortized cost per operation:** 2n/n = **O(1)** Though individual appends may cost O(n), the amortized cost is constant—most appends are cheap, and expensive ones are rare enough that the average remains low.