Skip to interview prep
Apexed

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.

What is amortized analysis? Explain it with a dynamic array. — Data structures & algorithms interview question — Apexed