#amortized-analysis
Dynamic Array
Dynamic Array A dynamic array maintains contiguous storage while allowing the number of elements to grow or shrink. When capacity is exhausted, it allocates a larger block and copies existing elements. You use it when the size is not known in advance but fast indexed access and cache locality still matter. Problem Maintain a sequence $A$ that supports: append an element read or write at index $i$ grow automatically when...
Amortized Analysis
Amortized Analysis Amortized analysis studies the total cost of a sequence of operations and divides it across the sequence. For dynamic arrays, a single append may be expensive when it triggers resizing, but many appends remain cheap on average. You use it when occasional costly operations are balanced by many cheap operations. Problem Given a dynamic array that doubles capacity when full, show that appending $n$ elements takes total time:...