Amortized Analysis

Math for CS · Axiom Academy

Analyzing average cost over sequences of operations Amortized analysis examines the average cost of operations in a sequence, rather than worst-case individual operations. Classic Example: Dynamic array resizing. Appending to a full array requires copying all elements, but this happens infrequently. Consider a dynamic array that doubles in size when full: Worst case for one append: O(n) if array is full Amortized cost: O(1) per append Why? After n appends requiring a resize at capacity c, c, 2c, 4c, ..., the total work is: Three Methods of Amortized Analysis For dynamic array with doubling: 2 goes to "bank" for future resize costs When resize happens, bank has enough to cover all copying Amortized cost: O(1) per operation Why amortized analysis matters: Dynamic arrays in Python, Java, C++ Many data structures perform well on average despite occasional expensive operations

This is the written version of the interactive lesson above. See the full Math for CS course.