# Amortized analysis of resizing array implementation of a stack

Here is an excerpt from the book Algorithms, 4th edition by R. Sedgewick and K. Wayne:

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.

It is unclear to me why 4N array accesses are required to grow the array. From my understanding, in the proof they describe the case when the array grows from size N to 2N, and for that it should require only 2N array accesses (copy the first N elements, 2 array accesses per element).

• I wouldn't fuss about constants. – Yuval Filmus Sep 28 '17 at 20:30

Q. Does int[] a = new int[N] count as N array accesses (to initialize entries to 0)?