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

If the stack has size $n$ at some time, then you will have performed $i$ size doublings so that after the last doubling the size $2^i$ is larger than $n$, that is $$2^i>n\ge2^{i-1}.$$ The cost of those doublings is the cited geometric sum with value $$1+2+4+...+2^{i-1}=2^i-1\le 2n-1,$$ as the text says.

Answer 2

$n$ is the number of operations, if $n=1$ then we don't need to resize the array (each array has at least 1 element);if we look at $1, 2,4,8,\cdots$ then $n$ is between two elements of the sequence i.e $n\in(2^i,2^{i+1}]$ for some $i$ ($n$ must be in some of those sets $(1,2],(2,4],(4,8],\ldots$) .

If we need to insert $n$ elements then having an array of size $2^{i+1}$ will suffice and size of $2^i$ will not suffice, to get to $2^{i+1}$ we doubled the size of a $2^i$ and copied the $2^i$ elements from that array to the new array which occurs a $2^i$ cost.

However we have that $2^i<n$ because $n\in(2^i,2^{i+1}]$, and similarly $$1+2+4+\cdots+2^i=2^{i+1}-1= 2\cdot 2^i-1\leq 2n-1$$