Big O Notation, Part Two: Space Complexity

Note: If you haven’t read our article on time complexity, it’s recommended to start there. Part two of this series assumes you are familiar with different possible Big O values.

In our first article about Big O Notation and time complexity, we talk about how much time it takes for the algorithm to complete when its input increases. This is important when we interact with very large datasets. A large dataset combined with a decent time complexity leads to more efficient algorithms. However, there is one more aspect to Big O Notation that needs to be considered: space complexity.

What is Space Complexity?

Time complexity and space complexity are similar as they relate to the amount of input an algorithm has. Where time complexity is related to the amount of operations an algorithm needs to perform to terminate, space complexity is related to the total amount of space needed to complete the algorithm. Space complexity is expressed in terms of Big O Notation. 

The space complexity includes the amount of space needed for the input as well as the auxiliary space needed in the algorithm to execute. Auxiliary space is the extra space used to store temporary data structures or variables used to solve the algorithm. Just like in time complexity, the Big O of an algorithm considers the worst case scenario, or the asymptotic upper bound.

Figuring Out the Space Required to Run an Algorithm

When we figure out the space complexity of an algorithm, take a look at two things: the input size and the auxiliary space needed to run the function. In most cases, we don’t reduce the size down to how many bytes the input is – we just look at the amount of memory the input or auxiliary space needs to use. 

The input of an algorithm is what gets passed into the function when it is invoked. Typically, this will be some sort of primitive value: string, number, or object. The exact size of each might differ based on language, but we can figure in a general sense how much space is needed.

Example with Simple Inputs and Output

public int subtract(int a, int b) {
   return a - b;
}

(Note: We are using Java here so you can easily discern the data types, but this can pretty much go for any language.)

Take the above function. The purpose of this function is to take an input – in this case two ints (short for integers) and return an output, also an int. 

In our input, we have two variables – int a and int b. Our returned value – an int – also takes up space as well. Because our integers are only evaluated once, we consider the space complexity here to be O(1) – constant time.

Example with More Complex Input

public int sumArray(int[] array) {
   int size = 0;
   int sum = 0;
   for (int i = 0; i < size; i++) {
       sum += array[i];
   }
   return sum;
}

This function has an array as its input. The array, not knowing the length, has n indices. The two variables in the first two lines of the function are O(1) since they are evaluated only once. The sum is an integer, is also O(1). The Big O for space complexity is O(n) to dictate the space for the array. 

Conclusion

The most efficient algorithm is one that takes the least amount of time and memory. It will be near impossible, if not impossible, though, to write an algorithm that will be able to satisfy both conditions. You ultimately have to sacrifice one for the other. The question becomes, which do you sacrifice?

The answer is: it depends. Everything depends on the requirements for the project or algorithm you are working on. If you only have minimal memory, you need to sacrifice time complexity to use the least space and vice versa.