Cost of Resizing

  • Determine the cost of dynamically resizing an array-based implementation of a stack.

Here is the implementation of push. 

@Override
public void push(T value) {
  data[numElements++] = value;
  if (numElements == capacity) {
    grow();
  }
}

We know grow() is O(n)\Omicron(n).

Exercise What is the running time of push?

Solution

The worst-case asymptotic running time of push is also O(n)\Omicron(n).

Consider the data array is constructed initially with the capacity of nn. We then perform n+1n+1 "push" operation one after another.

Exercise What is the worst-case running time of push per operation (rather than per algorithm).

Hint

We know the grow operation will only be called for the nthn^{th} push. Therefore,

  • the first time we call push, its cost is really O(1)\Omicron(1),
  • the second time we call push its cost is …\dots
  • …\dots
  • the nthn^{th} time we call push …\dots
  • …\dots
Solution

The cost of push is O(1)\Omicron(1) for the first n−1n - 1 pushes. Then, for the nthn^{th} push, we must grow the array, and so it will cost O(n)\Omicron(n). After that, the n+1n+1 push is again O(1)\Omicron(1).