If you have a dynamic array where the size $s$ becomes $4s$ when you fill the array and there are no delete operations. How much do you spend per insert?I am asking because when the size doubles, you only spend 3 dollars per insert (based on this analysis). But when you make the size 4 times bigger, then for some of the inserts you would need to spend 3\$ and for the rest you spend 2$?Is this right? Or do we always need to spend the same amount? And if there is extra we just store it in the bank?
amortized analysis accounting method
amortized analysis