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)$. If we store the blocks in (for example) an ArrayStack, then the amount of space wasted by the list that stores those $r$ blocks is also $O(r) = O(\sqrt n)$. The other space needed for storing $n$ and other accounting information is $O(1)$. Therefore, the total amount of wasted space in a RootishArrayStack is $O(\sqrt n)$.

Next, we argue that this space usage is optimal for any data structure that starts out empty and can support the addition of one item at a time. More precisely, we will show that, at some point during the addition of $n$ items, the data structure is wasting an amount of space at least in $\sqrt n$ (though it may be only wasted for a moment).

Suppose we start with an empty data structure and we add $n$ items one at a time. At the end of this process, all $n$ items are stored in the structure and distributed among a collection of $r$ memory blocks. If $r \ge \sqrt n$, then the data structure must be using $r$ pointers (or references) to keep track of these $r$ blocks, and these pointers are wasted space. On the other hand, if $r < \sqrt n$ then, by the pigeonhole principle, some block must have a size of at least $n/r > \sqrt n$ ...