How to write an algorithm which doubles stack in order to accommodate for new members where push is in constant time in the worst case?

Question

We're given the algorithm which uses stack in order to store data (stack is implemented via an array). When the stack is full the algorithm does the following:

1. Creates a new array double the size of the original one.
2. Copies all elements of the old array to the new array, preserving the order.

Adjust the algorithm so that the insertion of new element will be in constant time in the worst case.

The limitation here is we must use arrays as stack implementation.

The worst case is when for example the old stack of size $n$ is full and now we need to insert a new element. So we create a new stack $S_2$ of size $2n$ and we want to insert the new element to $S_2[n+1]$.

I'm stuck with the constant time requirement, I'd appreciate any hints to the right direction.

NB: I'm aware that the title is a bit general, I couldn't think of anything more specific, if you know under which category of algorithms it falls under please let me know and I'll edit the heading.

Answer 1

I don't think that it is possible to push an element to a full array-based stack in worst case $\mathcal{O}(1)$ time. However, you can rest assured that each push runs in constant amortized time whenever you multiply the length of the full array by a factor of $q > 1$ (like you do; $q = 2$ in your case). This is why:

Suppose the initial array capacity is $m$. Next we choose $q > 1$ such that $\lfloor qm \rfloor > m$, or namely, $q$ must be sufficiently large in order to trigger an array expansion.

Suppose the total accumulated work of adding $n$ elements to the stack is

$$W = m + mq + mq^2 + \dots + \overbrace{mq^k}^n$$.

We require $k$ to be the smallest integer such that $mq^k \geq n$, which leads us to the following inequalities:

$$ \begin{aligned} mq^k &\geq n \\ q^k &\geq \frac{n}{m} \\ \log_q q^k &\geq \log_q \Bigg( \frac{n}{m} \Bigg) \\ k &\geq \log_q n - \log_q m. \end{aligned} $$

Since $k$ is required to be the smallest integer satisfying the above inequality, we can set $k = \lceil \log_q n - \log_q m \rceil$. Also,

$$ \begin{align} qW = mq + mq^2 + \dots + mq^{k + 1} &\Rightarrow W - qW = m(1 - q^{k+1}) \\ &\Rightarrow W = m\frac{1 - q^{k+1}}{1-q}. \end{align} $$

Since $k = \lceil \log_q n - \log_q m \rceil$, we obtain $$ \begin{align} W &= m\frac{1 - q^{\lceil \log_q n - \log_q m \rceil + 1}}{1 - q} \\ &\leq m\frac{1 - q \cdot q^{\lceil \log_q n \rceil}}{1 - q} \\ &\leq m \frac{1 - q \cdot q^{\log_q n + 1}}{1- q} \\ &= m \frac{1 - q^2n}{1 - q}. \end{align} $$

Now we have that

$$ \begin{align} \frac{1}{n} W &\leq \frac{1}{n} \Bigg[ m \frac{1-q^2n}{1-q} \Bigg] \\ &= \frac{1}{n} \Bigg[ \frac{m}{1-q} - \frac{nmq^2}{1-q} \Bigg] \\ &= \frac{m}{(1-q)n} - \frac{mq^2}{1-q} \\ &\leq \frac{m}{1-q} - \frac{mq^2}{1-q} \\ &= \frac{m(1-q^2)}{1-q} \\ &= \frac{m(1+q)(1-q)}{1-q} \\ &= m(1+q), \end{align} $$ which is constant since $m$ and $q$ are fixed parameters independent of $n$.

Answer 2

If you use one array for storage, and you add more and more items to the stack, then at some point you need to increase the size of the array. Most likely your "array" implementation doesn't allow increasing the array size in constant time.

So the only possible solution: Reserve all available space for the array, at the time the stack is created, that is before adding the first item. Since all available space has been reserved, it is impossible to increase the array size, so all operations can be done in constant time.

It is kind of cheating though.