Analysis of RootishArrayStack
Explore the advantage of using RootishArrayStack.
We'll cover the following...
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 . In some environments, this takes only constant time, while in others, it may require time proportional to .
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 elements have been added or removed. Therefore, even if grow()
and shrink()
take time, this cost can be amortized over at least add(i, x)
or remove(i)
operations, so that the amortized cost of grow()
and shrink()
is 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, , used by a RootishArrayStack
that stores elements therefore satisfies
Again, using the quadratic equation on this gives
The last two blocks have sizes and , so the space wasted by these two blocks is at most . If we store the blocks in (for example) an ArrayStack
, then the amount of space wasted by the List that stores those blocks is also . The other space needed for storing and other accounting information is . Therefore, the total amount of wasted space in a RootishArrayStack
is .
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 (though it may be only wasted for a moment).
Suppose we start with an empty data structure and we add items one at a time. At the end of this process, all items are stored in the structure and distributed among a collection of memory blocks. If , then the data structure must be using pointers (or references) to keep track of these blocks, and these pointers are wasted space. On the other hand, if then, by the pigeonhole principle, some block must have a size of at least ...