4. What is amortized analysis? Explain it with a dynamic array.
MediumAlgorithm analysis
Technical
Show model answer
Amortized analysis averages the cost of a sequence of operations, guaranteeing the average per operation even if some single operations are expensive.
Appending to a dynamic array is usually O(1), but occasionally the array doubles and copies n elements. Over n appends the total copying is at most 1 + 2 + 4 + … < 2n, so each append costs O(1) amortized.