Amortized dynamic stack counterpart

Question

The following is a snippet of text about the amortized analysis of a dynamic stack.

If we implement the stack as a dynamic array. Say this is an insertion into the cost of array 1, taking an element from the cost of array 1, and the cost of changing the size of the array is the number of elements moved. (Say that all other operations, such as increasing or decreasing the "top" are free). If we decide to double the size of the array when we are the size. Now, in any sequence of operations “n”, the total cost is a change in size 1 + 2 + 4 + 8 + ... + (2 ^ i) (i.e. 2 to degree i) for some 2 ^ i <n (if all operations are pushed, then (2 ^ i) will be the greatest power from 2 less than n). The sum is at most 2n - 1. Adding “n” to the extra cost for insertion / deletion, we get a total cost of <3n, and the arithmetic cost of operations is <3.

My question is how the author came to the conclusion that the sum is not more than 2n -1. Request for help with an example or proof.

Thanks!

Answer 1

this is the sum of the 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 

Answer 2

You are trying to find the amount:

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

We see that this is the same as:

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

Denote this sum by S(i) . Looking at the first few values, you can see the 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 see that they all seem to be one less than 2 degrees. More precisely: S(i) seems to be equal to 2^(i+1) - 1 . We can prove this by induction:

Base register:

 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) 

as can be seen from the definition of the amount. In addition, 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 integers i >= 0 , that S(i) = 2^(i+1) - 1

Now, returning to the original question, we are given that 2^i < n . Then we have:

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

and therefore we have proved that S (i) 2 * N + 1.