Amortized Cost Analysis with a Stack

Suppose I have a stack backed by an n-element array with cost 1 to push, cost 1 to take an element out of the array, and the cost of resizing the array is the number of elements moved.

1) Every time the stack becomes full, I copy over the current n elements into a new array that's one element larger than before. My text claims that a series of n pushes will result in a total cost of:

1 + 2 + 3 + ... + n

Why is this? Say my array starts off with n = 1.

I push and the stack is now full (cost 1) I increment size of array (n = 2 and cost of 2) I push and stack is now full (cost of 1) I increment size of the array (n = 3 and cost of 4) ...

What am I missing?

2) Suppose I double the size of the array every time the stack is full. Now I have a series of n pushes starting with a 1-element array:

I push and the stack is now full (cost of 1) I double array size and copy 1 element over (cost of 2, n = 2) I push and stack is now full (cost of 1) I double array size and copy 2 elements over (cost of 4, n = 4) ...

Does this analysis look right?

For a series of n pushes, it would yield 1 + 2 + 1 + 4 + 1 + 8 + ... + 1 + 2 ^ (n/2)

Solution

Everything sounds reasonable to me:

1) Let's start with an empty stack, represented by an array of initial size n=1

push 1. element => cost = <push-cost> = 1 => array now full
push 2. element => cost = <resize-cost> + <push-cost> = n + 1 = 2 => n := n + 1 = 2
push 3. element => cost = <resize-cost> + <push-cost> = n + 1 = 3 => n := n + 1 = 3

...and so on, which indeed results in total cost of 1 + 2 + 3 + ... + n when pushing n elements.

2) You don't say what your text says about this behavior, but the calculation is similar:

push 1. element => cost = <push-cost> = 1 => array now full
push 2. element => cost = <resize-cost> + <push-cost> = n + 1 = 2 => n := 2 * n = 2
push 3. element => cost = <resize-cost> + <push-cost> = n + 1 = 3 => n := 2 * n = 4
push 4. element => cost = <push-cost> = 1 => array now full
push 5. element => cost = <resize-cost> + <push-cost> = n + 1 = 5 => n := 2 * n = 8
push 6. element => cost = <push-cost> = 1
push 7. element => cost = <push-cost> = 1
push 8. element => cost = <push-cost> = 1 => array now full
push 9. element => cost = <resize-cost> + <push-cost> = n + 1 = 9 => n := 2 * n = 16

...which results in total costs of

1 + 2 + 3 + 1 + 5 + 1 + 1 + 1 + 9 + 1 + 1 + 1 + 1 + 1 + 1 + 1...

Note how resize operations always happen at an element 2^n+1, followed by 2^n-1 "resize-free" operations. As a result, we can rewrite that as (collapse + 1-chains to the left)

1 + 2 + 4 + 8 + 16 + ...

which (informally) indicates total costs of O(n) or amortized costs of O(1) per push-operation.