Cost analysis for implementing a stack as an array?

Question

Please Refer to answer 2 of the material above. I can follow the text up to that point. I always seem to loose conceptualisation when there's no illustration maybe due to the fact that I'm new to math notation.

I understand the cost for an expensive operation (double the array when the stack is full)

1 + 2 + 4 + 8 + ... + 2^i where i is the index of that sequence. So index 0 = 1, 1 = 2, 2 = 4 and 3 = 8.

I can see the sequence for costly operations but I get confused with the following explanation.

Now, in any sequence of n operations, the total cost for resizing is 1 + 2 + 4 + 8 + ... + 2^i for some 2^i < n (if all operations are pushes then 2^i will be the largest power of 2 less than n). This sum is at most 2n − 1. Adding in the additional cost of n for inserting/removing, we get a total cost < 3n, and so our amortised cost per operation is < 3

I don't understand that explanation?

the total cost for resizing is 1 + 2 + 4 + 8 + ... + 2^i for some 2^i < n

What does it mean for some 2^i < n

does it say that the number of operations n will always be larger than 2^i? and does n stand for the number of operations or the length of the array?

And the following I just don't follow:

if all operations are pushes then 2^i will be the largest power of 2 less than n. This sum is at most 2n − 1.

Could someone illustrate this please?

Answer 1

n is the largest stack size, intrinsic array size at this moment is the least power of two 2^(i+1)>=n, so the last operation of expansion takes 2^i<n time.

For example, if array reaches size n=11, the last expansion causes grow from 8 to 16 with 8 items moved

About the second question: sum of geometric progression

1 + 2 + 4 + 8 + ... + 2^i = 2^(i+1) - 1