Algorithms and Data Structures · Senior · Question 28 of 75
What is amortized analysis with the "accounting" or "potential" method?
- 1Measuring the time of an operation many times and averaging
- ✓Correct answer: Charging cheap operations extra to pay for rare expensive ones
- 3Averaging running time over random inputs
Explanation
It gives a worst-case bound for a sequence of operations, with no probability involved. Each push to a dynamic array "saves" a constant that later pays for copying during a resize. Averaging over random inputs is average-case analysis, a different thing.