Supposed an array is initially empty with a size 5, and it expands by 5 everytime all slots are filled.
I understand that if we are only considering any sequence of n append() operations, the amortized cost would be O(n) because the total cost would be:
5+(5+1＊5)+（5＋2＊5)＋...+(5＋(floor(n/5)-1)*5) = O(n^2).
*where floor(n/5) is the number of array expansions.
However, what if it's any sequence of n operations contains pop() as well? Assume pop() doesn't change array size.
My way obviously wouldn't work and I have read the CLRS but am still quite stucked. Any help would be appreciated.
The answer, somewhat disappointingly, is if your sequence contains s many push or pop operations then the amortized cost of each operation is O(s).
To cherry-pick a line from another question's very good answer:
Amortized analysis gives the average performance (over time) of each operation in the worst case.
The worst case is pretty clear: repeated pushes. In which case, your original analysis stands.