Return to Answer

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

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$.

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$.

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

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 = \overbrace{m + mq + mq^2 + \dots + 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$.

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$.