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 $\Omicron(n)$.

Exercise What is the running time of push?

Solution

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

Consider the data array is constructed initially with the capacity of $n$. We then perform $n$ "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 $n^{th}$ push. Therefore,

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

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