Big O: Space Complexity

Big O is a big deal when it comes to algorithms. And I don't know if it's just me, but I feel like I spent a lot more time understanding time complexity rather than space complexity. It makes sense that as applications scale, space would become an important issue, but that's usually a second thought after how much initial time the algorithm will take. Also, people love to say that memory is cheap!

But space complexity is still a very important part of Big O notation and I think it's definitely worth going over so you're prepared for your next technical interview.

I do want to emphasize here though, that this is not going to be a deep dive into the formal calculated intricacies of space complexity. I just wanted to go over this concept on a basic level that would be appropriate for a simple explanation of an algorithm.

Overview: What is space complexity?

I think GeeksforGeeks does an awesome job of explaining it clearly, but in case you don't want to click that link, here is how they define it:

"Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input."

They go on to talk about auxiliary space which is also very important:

"Auxiliary Space is the extra space or temporary space used by an algorithm."

So to summarize, space complexity is how much total space the algorithm will take up but auxiliary space is how much space could be used temporarily to run part of an algorithm. Auxiliary space ignores the input size of the data structure that you begin with and accounts for any program calls inside of the function.

They then give a great example about the space complexity of the different sorting methods:

"Merge Sort uses O(n) auxiliary space, Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n) though."

If you need a refresher on a few of these algorithms, you can check out my sorting series in Ruby!

But knowing these sorting algorithms, we can infer that insertion sort and heap sort are both in-place sorting algorithms. Meaning they only modify the existing array, which has already been accounted for (input) in terms of space, and won't require extra space to complete. Contrast this with merge sort which is not an in-place sorting algorithm and requires that a new array be created each time the original array is halved.

Thus it makes sense that merge sort uses more auxiliary space than insertion or heap sort, but in the end all three of these algorithms still have a total space complexity of O(n). If that isn't clear, here is a quote from the Bluffer's Guide to Space Complexity that really helped it to make more sense to me:

Space complexity is a measure of the amount of working storage an algorithm needs. That means how much memory, in the worst case, is needed at any point in the algorithm. As with time complexity, we're mostly concerned with how the space needs grow, in big-Oh terms, as the size N of the input problem grows.

Calculating Space Complexity

When we talk about big O, we know that time and space complexities tend to deal with this value n. Typically n represents the number of elements in a given data structure and can determine the amount of bytes needed to execute a function. Some languages like Java and C++ require that you allocate the amount of space needed to declare a data structure before even adding anything into it! Without going too far, I want to simply make you aware of the fact that space is calculated in terms of bytes. Essentially n would be the number of elements but also the amount of bytes that would be required to execute a function.

With that in mind, we can break down the memory consumption of an algorithm into three different parts that mainly affect the space complexity:

• variables and constants
  • Any function or algorithm that is based purely in variables or constants that are fixed and do not change over time will be measured as O(1) or constant space. These variables or constants will always take up the same amount of memory and thus do not need to be re-calculated for space after the program finishes running.
• inputs
  • The initial parameters we are given to begin the function are important for space complexity. If we are given an array then we already know that there will need to be space allocated for the amount of elements in the array.
• execution
  • Some functions will run and be completed right away, whereas some functions could be recursive or call other functions inside of itself. These functions could hold other functions on the stack waiting to be executed while it finishes. Space complexity is different for both of these situations. If a function completes as soon as it is called, no extra space is needed for it to be done. But in the case of a recursive function or a function calling another function inside of itself, extra space is needed in order to hold the values that are waiting to be executed.

Examples

Here are a few very basic examples of how to calculate space complexity:

1)

def get_sum(x, y, z)
  sum = 0
  sum = x + y + z
  return sum
end

For this example, we can see that there are only 3 parameters and 1 variable that we need to worry about. All of these values are fixed and will not change in the future. Therefore the space complexity overall will be O(1).

2)

def get_sum(array)
  sum = 0
  for i in [0...array.length]
    sum += array[i]
  end
  return sum
end

For this example we have our sum variable, but we also have a for loop. Any loop will take up as much space as the length of the item we are looping over. In this case we need to loop through the array to find out the total of all of the values in the array, thus our space complexity will be O(n) or linear where n is the number of elements in our array. This is because the space will continue to increase at the same rate as n will. If we think of a linear graph, it is simply a diagonal line as the values increase proportionally, as n gets larger so does the amount of space needed.

3)

def get_sum(array)
  size = array.length
  if size == 1
    return array[0]
  else
    return (array[0] + get_sum(array[1...size]))
  end
end

This last example I wanted to include because it brings up the issue of recursion and space complexity. We can see here that the function is calling itself multiple times and what would you guess is the space complexity? It's actually O(n) because each time the function calls itself again, space needs to be made for the value to being stored on the stack, waiting for execution. Compared to its iterative counterpart, this takes up much more space where an iterative approach would use the same variable space over and over again, thus being only O(1).

Resources

I wouldn't have been able to compile this blog post if it wasn't for the thoughtful explanation of others. Here are a few of the articles and videos I found really helped further my understanding:

• Bluffer's Guide to Space Complexity
• Space Complexity of Algorithms
• Big O Cheat Sheet
• Big O in Ruby (Also the big O graph is from this article, thanks!)

Thanks for reading and as always, if you have something to add please leave a comment below. Thanks and happy coding!