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$
1
  • $\begingroup$ I wouldn't fuss about constants. $\endgroup$ Sep 28, 2017 at 20:30

1 Answer 1

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$
2
  • 1
    $\begingroup$ Why is initialization necessary? Also, even considering initialization, we only get 3N operations. $\endgroup$ Sep 29, 2017 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, 2017 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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