Time and Space Complexity

Solution

The amount of work an algorithm does as a function of the input size. We count primitive operations (steps). In the model of computation we use, each primitive step takes constant time, so the running time is proportional to the step count.

Solution

Time. By convention a complexity claim with no resource named is about time. When memory is meant, the claim says space complexity.

Solution

Space complexity is the total memory an algorithm needs, as a function of the input size. Input space is the memory the input itself takes. Auxiliary space is the extra memory the algorithm allocates while it runs. Space complexity $=$ input space $+$ auxiliary space.

Exercise

Here are two methods that each return an array holding the elements of arr doubled. The first returns a new array. The second doubles the elements in place and returns arr itself.

public static int[] doubledCopy(int[] arr) {
  int[] out = new int[arr.length];
  for (int i = 0; i < arr.length; i++) {
    out[i] = 2 * arr[i];
  }
  return out;
}

public static int[] doubledInPlace(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    arr[i] = 2 * arr[i];
  }
  return arr;
}

Fill in the table, with $n$ the length of arr.

Method	Time	Space complexity	Input space	Auxiliary space
`doubledCopy`
`doubledInPlace`

Solution

Method	Time	Space complexity	Input space	Auxiliary space
`doubledCopy`	$O (n)$	$O (n)$	$O (n)$	$O (n)$
`doubledInPlace`	$O (n)$	$O (n)$	$O (n)$	$O (1)$

Both make one pass over $n$ elements. doubledCopy allocates a second array of length $n$ . doubledInPlace allocates only the loop index.

Solution

When algorithms work on the same input, the input space is the same. Including it in the total can hide differences in auxiliary space: the two doubling methods above both have $O (n)$ total space, even though one uses $O (n)$ auxiliary space and the other uses $O (1)$ . Comparing auxiliary space makes that difference visible. Total space can still distinguish algorithms when their extra memory grows faster than the input space.

Exercise

Here is add on a DynamicArray of int values. The field arr is the internal array, size is how many of its slots are in use, and grow allocates an array of twice the capacity, copies the size elements into it, and makes it the new arr.

public class DynamicArray {
  private int[] arr;
  private int size;

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

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

With $n$ the number of stored elements, what counts as the input space of add, and why? Then give the input space, the auxiliary space, and the space complexity of add in the best case and in the worst case.

Solution

The input includes the object add runs on, not just its parameter. add reads and writes arr and size, so the backing array counts as input space. For an array built by additions from a fixed initial capacity, the input space is $O (n)$ , as shown below. (To be more careful, we should count the input space as $O (capacity)$ : removing elements decreases $n$ but does not shrink the backing array. In that case, the best-case total space is also $O (capacity)$ .)

`add`	Input space	Auxiliary space	Space complexity
Best case	$O (n)$	$O (1)$	$O (n)$
Worst case	$O (n)$	$O (n)$	$O (n)$

In the best case arr has room and add allocates nothing. In the worst case arr is full and grow allocates bigger, with $2 n$ slots.