Analysis of RootishArrayStack

Growing and shrinking

Note that, unlike the ArrayStack.resize() operation, grow() and shrink() do not copy any data. They only allocate or free an array of size $r$. In some environments, this takes only constant time, while in others, it may require time proportional to $r$.

We note that, immediately after a call to grow() or shrink(), the situation is clear. The final block is completely empty, and all other blocks are completely full. Another call to grow() or shrink() will not happen until at least $r − 1$ elements have been added or removed. Therefore, even if grow() and shrink() take $O(r)$ time, this cost can be amortized over at least $r − 1$ add(i, x) or remove(i) operations, so that the amortized cost of grow() and shrink() is $O(1)$ per operation.

Space usage

Next, we analyze the amount of extra space used by a RootishArrayStack. In particular, we want to count any space used by a RootishArrayStack that is not an array element currently used to hold a list element. We call all such space wasted space.

The remove(i) operation ensures that a RootishArrayStack never has more than two blocks that are not completely full. The number of blocks, $r$, used by a RootishArrayStack that stores $n$ elements therefore satisfies

$$(r − 2)(r − 1) \le n$$

Again, using the quadratic equation on this gives

$$r \le (3 + \sqrt{1+4n})/2 = O(\sqrt n)$$

The last two blocks have sizes $r$ and $r − 1$, so the space wasted by these two blocks is at most $2r−1 = O(\sqrt n)$ ...