2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I fixed a mistake in my answer. Check it out. $\endgroup$ – coderodde Jun 11 '17 at 7:11
3
$\begingroup$

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}}{} \\ &\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}, \end{align} $$ which is constant since $m$ and $q$ are fixed parameters independent of $n$.

$\endgroup$
  • $\begingroup$ Thank you that is great detail! I didn't understand why $m$ is fixed though. Our initial array is of size $m$ according to your notation so the size of total work depends on $m$, no? $\endgroup$ – Yos Jun 10 '17 at 18:54
  • $\begingroup$ @Yos $m$ is just the initial capacity of the array (you have to start from some array, right?). Of course, each push depends on it, but the point is that we don't change its value during computation. $\endgroup$ – coderodde Jun 10 '17 at 18:56
  • $\begingroup$ Right, but the size of the next array is $2m$ then $4m$ etc so $m$ is a variable in my understanding $\endgroup$ – Yos Jun 10 '17 at 18:57
  • 1
    $\begingroup$ @Yos $n$ (the number of elements in the stack) is variable, $m$ is not. $\endgroup$ – coderodde Jun 10 '17 at 18:58
  • $\begingroup$ But then what is $m$? Is it not the size of the stack? $\endgroup$ – Yos Jun 10 '17 at 18:59
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But this contradicts the given algorithm as it stipulates that we create a new array with double the space of the original one $\endgroup$ – Yos Jun 10 '17 at 19:03
  • $\begingroup$ @Yos: This method will never create a new array that doesn't have double the size of the previous one. $\endgroup$ – gnasher729 Jun 11 '17 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.