algorithm - Amortized Cost Analysis with a Stack -

suppose have stack backed n-element array cost 1 push, cost 1 take element out of array, , cost of resizing array number of elements moved.

1) every time stack becomes full, copy on current n elements new array that's 1 element larger before. text claims series of n pushes result in total cost of:

1 + 2 + 3 + ... + n

why this? array starts off n = 1.

i push , stack full (cost 1) increment size of array (n = 2 , cost of 2) push , stack full (cost of 1) increment size of array (n = 3 , cost of 4) ...

what missing?

2) suppose double size of array every time stack full. have series of n pushes starting 1-element array:

i push , stack full (cost of 1) double array size , copy 1 element on (cost of 2, n = 2) push , stack full (cost of 1) double array size , copy 2 elements on (cost of 4, n = 4) ...

does analysis right?

for series of n pushes, yield 1 + 2 + 1 + 4 + 1 + 8 + ... + 1 + 2 ^ (n/2)

everything sounds reasonable me:

1) let's start empty stack, represented array of initial size n=1

• push 1. element => cost = <push-cost> = 1 => array 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 on, indeed results in total cost of 1 + 2 + 3 + ... + n when pushing n elements.

2) don't text says behavior, calculation similar:

• push 1. element => cost = <push-cost> = 1 => array 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 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 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 happen @ element 2^n+1, followed 2^n-1 "resize-free" operations. result, can rewrite (collapse + 1-chains left)

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

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