So I have been struggling with amortized analysis on dynamic arrays. I have studied through the University of Torontos slides on this topic and this
When the array is ½ full after DELETE, create a new
array of half of the size, and copy all the elements.
Consider the following sequence of operations
performed on a full array with n element…
APPEND, DELETE, APPEND, DELETE, APPEND, …
Ɵ(n) amortized cost per operation since every
APPEND or DELETE causes allocation > > > of new array.
especially does not make sense to me.
Is it O(n) because every append and delete operation is dependent on how big n is? But even then, do the costs not increase in a constant manner?
Appreciate any help!