Amortized anlysis of dynamic stack

F开发者_开发技巧ollowing is text snippet regarding amortized ananlysis of dynamic stack.

If we are implementing stack as a dynamic array. Say that inserting into the array costs 1, taking an element out of array costs 1, and the cost of resizing the array is the number of elements moved. (Say that all other operations, like incrementing or decrementing "top" are free). If we decide to double the size of the array when we resize. Now, in any sequence of "n" operations, the total cost for resizing is 1 +2 + 4+8 +...+(2^i) (i.e, 2 to power of i) for some 2^i < n ( if all operations are pushes then (2 ^i) will be largest power of 2 less than n). The sum is atmost 2n - 1. Adding in the additional cost of "n" for inserting/removing, we get a total cost < 3n, and our amoritzed cost per operations is < 3.

My question is how author came to conclusion that sum is at most 2n -1. Request to help with example or proof.

Thanks!

it is the sum of a geometric progression :

SUM(q^k for k = 0 to n) = (q ^n+1 -1)/ (q-1)

then in your case you have :

SUM(2^k for k = 0 to i) = 2^(i+1) - 1 

Then since 2^i < n

2^(i+1) < 2n 

and

SUM(2^k for k = 0 to i) = 2^(i+1) - 1 < 2n - 1

You are trying to find the sum:

1 + 2 + 4 + ... + 2^i

We can see this is the same as:

2^0 + 2^1 + ... + 2^i

Let's denote this sum as S(i). Looking at the first few values, you may see a pattern:

S(0) = 2^0       = 1         = 1
S(1) = 2^0 + 2^1 = 1 + 2     = 3
S(2) = ...       = 1 + 2 + 4 = 7
S(3) = ...       = ...       = 15
S(4) = ...       = ...       = 31

We can see that they all seem to be one less than powers of 2. To be more exact: S(i) seems to equal 2^(i+1) - 1. We can prove this by induction:

Base case:

S(0) = 2^(0+1) - 1

We can trivially see that the above statement is true.

Inductive step:

We know that:

S(i) = S(i-1) + 2^(i)

which is evident from the definition of the sum. Furthermore, if S(i-1) = 2^(i) - 1 then:

S(i) = (2^(i) - 1) + 2^(i)
       = 2*(2^(i)) - 1
       = 2^(i+1) - 1

and therefore, we have proved that for all integer i >= 0 that S(i) = 2^(i+1) - 1

Now, going back to your original question, we are given that 2^i < n. We then have:

S(i) = 2^(i+1) - 1
     = 2*(2^i) - 1
     < 2*n - 1

and therefore, we have proven that S(i) < 2*n+1.