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