Complexity of grow and add

There is one part of a complexity claim we have not looked at yet: whether it is about a single operation or a sequence of them. DynamicArray.add is the example for that, because a single call and a long run of calls tell very different stories about it.

Let’s do the single call first. We have time, space, best case, and worst case now, so let’s apply all of them to add and to the grow that add calls when the array is full.

Here is grow:

private void grow() {
  int[] bigger = new int[arr.length * 2];
  for (int i = 0; i < size; i++) {
    bigger[i] = arr[i];
  }
  arr = bigger;
}

Let $n$ be the number of elements stored in the array.

Time is $O(n)$. Creating bigger takes $O(n)$ time, because Java initializes all $2n$ slots to zero. The loop then runs $n$ times, copying one element each pass, and one copy is a constant amount of work. Reassigning arr is one step. Both array creation and copying take $O(n)$ time, so the total time is $O(n)$.

Space is $O(n)$. The input space is $O(n)$, because grow starts with the original array arr, which holds $n$ elements. The auxiliary space is the new bigger array, which holds $2n$ slots. Big-Oh suppresses the coefficient, so $2n$ is $O(n)$ as well. Both parts are $O(n)$, so the total is $O(n)$.

Now consider the add method, which calls grow when the array is full:

public void add(int value) {
  if (size == arr.length) {
    grow();
  }
  arr[size] = value;
  size++;
}

The if at the top of add gives us two cases, so let’s take them separately. Which case we are in depends on whether the array is full, so this is a best-case and worst-case question.

Best case: the array is not full. The if condition is false, so add skips grow, writes one slot, and increments size. That is a fixed number of steps regardless of $n$, so the time is $O(1)$. The auxiliary space is $O(1)$ too, because add allocates nothing. The input space is $O(n)$. The only parameter is value, but add is a method on a DynamicArray object, so it starts with the object’s fields too. The input is whatever the method starts with, and that includes arr, which holds $n$ elements. So the space complexity is $O(n)$, and all of that is input space. (To be more careful, we should count the input space as $O(\text{capacity})$: removing elements decreases $n$ but does not shrink the backing array.)

Worst case: the array is full. Now the if condition is true and add calls grow. We just worked out that grow costs $O(n)$ time and allocates $O(n)$ auxiliary space. After grow returns, add writes one slot and increments size, which is a constant amount of work. So the whole call is $O(n)+O(1)$, which is $O(n)$ time, and the auxiliary space is the new array grow allocated, $O(n)$.

By our convention that an unqualified Big-Oh means the worst case, add has a time complexity of $O(n)$ and a space complexity of $O(n)$.