Proposition E. In the resizing array implementation of Stack
(Algorithm 1.1),
the average number of array accesses for any sequence of operations
starting from
an empty data structure is constant in the worst case.
Proof sketch: For each push() that causes the array to grow ( say
from size N to
size 2N), consider the N/2 - 1 push() operations that most recently
caused the
stack size to grow to k, for k from N/2 + 2 to N. Averaging the 4N
array accesses to
grow the array with N/2 array accesses (one for each push), we get
an average cost
of 9 array accesses per operation. Proving that the number of array
accesses used by
any sequence of M operations is proportional to M is more intricate
(see Exercise
1.4.32)
Explain the proposition in detail, also redo the work assuming
we are tripling the array. Please use same wording as the
proposition.