Space Complexity

Every claim so far has been about time. Now let’s measure memory instead.

Space complexity is the amount of memory an algorithm needs to run to completion, as a function of the size of its input. We can use the same Big-Oh notation to express space complexity as we do for time complexity.

We can think of space complexity as the total memory an algorithm needs, including the input itself and any extra memory it allocates on its own. The extra memory is called auxiliary space. Auxiliary space is what we usually care about when we compare algorithms, because the input space is the same for all algorithms that solve the same problem, so it does not tell them apart.

Here are two ways to reverse an array. The first one swaps from both ends inward:

public static <T> void reverse(T[] arr) {
  for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
    T temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

The second one copies into a new array and writes it back:

public static <T> void reverse(T[] arr) {
  int n = arr.length;
  T[] tmp = (T[]) new Object[n];
  for (int i = 0; i < n; i++) {
    tmp[i] = arr[n - i - 1];
  }
  for (int i = 0; i < n; i++) {
    arr[i] = tmp[i];
  }
}

For each version, let’s give its time and its space complexity (broken into input space and auxiliary space):

`reverse`	Time	Space complexity	Input space	Auxiliary space
In place	$O (n)$	$O (n)$	$O (n)$	$O (1)$
Into a copy	$O (n)$	$O (n)$	$O (n)$	$O (n)$

Both run in $O (n)$ time. The first version makes one pass, swapping a pair each iteration. The second version makes two passes, one to fill tmp and one to copy it back, and two passes over $n$ elements is still $O (n)$ .

Both also have $O (n)$ space complexity, because the input array by itself is already $O (n)$ and nothing either version allocates is bigger than that. So neither the time nor the total space tells the two apart.

The auxiliary space tells them apart. The first version allocates only temp, a single variable, so its auxiliary space is $O (1)$ no matter how long the array is. The second version allocates a tmp array of the same length as the input, so its auxiliary space is $O (n)$ .

The first version is an example of an algorithm that works in place: it modifies its input using $O (1)$ auxiliary space. The name comes from what the code does. It moves the elements around inside the array it was given, rather than building the result somewhere else and copying it back. We will meet the term again when we study sorting, where whether a sort works in place is one of the main things that separates one algorithm from another.