0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I wouldn't fuss about constants. $\endgroup$ – Yuval Filmus Sep 28 '17 at 20:30
2
$\begingroup$

They include the initialization of the new array.

From page 207 of the text:

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

A. Most likely yes, so we make that assumption in this book, though a sophisticated compiler implementation might try to avoid this cost for huge sparse arrays.

$\endgroup$
  • 1
    $\begingroup$ Why is initialization necessary? Also, even considering initialization, we only get 3N operations. $\endgroup$ – Yuval Filmus Sep 29 '17 at 6:36
  • 1
    $\begingroup$ @YuvalFilmus It's not in this case but the book focuses on Java which in most implementations will initialize new arrays in linear time. If we resize a size N stack then we have initialization of 2N array, N reads, and N writes for total of 4N. $\endgroup$ – Tomoki Sep 29 '17 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.