1

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.

Pig
  • 2,002
  • 5
  • 26
  • 42
  • You seem to be inserting at the end of the array only (because there is no cost associated to moving items around in your formula) so is the delete operation at the end of the array only ("pop") or do you want to cater for deletes at arbitrary points of the array (in which case you would need to move objects around)? – Antti Huima Oct 27 '14 at 08:01
  • There's too little specified for this to be a reasonable question to answer: What's the cost of expanding an N-length array? Where are you wanting to delete? When you delete, do the 'high' elements slide down, or can you plug the hole with the last element? Or can you just leave the element 'empty'? The costs you have and semantics you need to maintain aren't clear. – Kaganar Oct 27 '14 at 15:08
  • @AnttiHuima Sorry, they should work like append and pop. – Pig Oct 27 '14 at 16:03
  • @Kaganar Sorry, they should work like append and pop. And array size doesn't need to be changed after pop – Pig Oct 27 '14 at 16:04

1 Answers1

1

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.

Community
  • 1
  • 1
Kaganar
  • 6,540
  • 2
  • 26
  • 59
  • Thanks for the answer, but in your last line, does it mean the worst case does not pop() at all? – Pig Oct 27 '14 at 20:40