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!

Comments

[mosmn]

Here from Odin, just wanted to point something out.

Your explanation of the space complexity is mostly accurate. However, in the given code snippet (example 2), the space complexity is actually O(1), meaning it is constant and not directly proportional to the input size (n).

Space complexity measures the additional space or memory required by an algorithm based on the input size. In this code, the space used remains constant, regardless of the size of the input array.

The only additional space used in this code is for the variable sum, which is a single integer. It doesn't depend on the size of the array itself, but rather on the number of elements present in the array. Consequently, the space complexity is constant, denoted as O(1).

It's important to distinguish space complexity from the space required to store the input data. In this case, the space complexity of the code is independent of the input array's size.

However, if you were to introduce a copy of the array and utilize that copy in the code, it would indeed increase the space complexity. Let's examine the modified code:

def get_sum(array)
  array_copy = array.clone()  # Create a copy of the array
  sum = 0
  for i in [0...array_copy.length]
    sum += array_copy[i]
  end
  return sum
end

With this modification, the array_copy variable is introduced to hold a copy of the original array.

Since we are now allocating additional memory to store the copied array, the space complexity becomes dependent on the size of the input array. Consequently, the space complexity would be O(n), where n represents the number of elements in the array.

[Gus]

Here from TOP too and the lesson on memory complexity states:

'When a data structure is passed in as the argument, especially for languages that pass arrays by reference rather than value, it can be a bit unclear if that method considers the space used by that data structure when calculating its space complexity. If we didn’t count it, then it would be easy for all our methods to have great space usage on paper because we put the onus on the caller to allocate that space. If we did count it, but the data structure was created for use by many different methods, then the space complexity for all those methods is O(N) when they aren’t utilizing additional space. Then consider that if your method receives an array as an input and loops it, an index must be created for the loop which uses additional space.

..Ultimately when you consider Big O measures the worst-case scenario, it would be easier to err on the side of caution and do consider the space of arguments passed to your method."

So wouldn't the space complexity be O(n) and the auxiliary space is what would be O(1)? Let me know if I'm misunderstanding something

[iamashay]

Many sources seem to define space complexity as input space plus the auxiliary space. Since, the input array can have "n" elements so the space complexity is considered as O(n), I think.

Refer to the second example here: courses.cs.northwestern.edu/311/ht...

[David Islam]

I always thought of space complexity as just auxiliary storage, which makes more sense in my opinion...

[idontwannatell]

Here from Odin also, I think that the space complexity depends if the argument is a reference to the original variable or just a copy. Because for instance if the function is recursive then every time it is being called it is creating a copy of the input then it will definitely use more memory on the other hand if its a reference that's just O(1) times the recursive calls.
Let me know if I am wrong...

[Ovi]

mosmn's correction would also solve the contradiction arising in example 3: "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)." But the iterative example above, number 2, had O(n) as space complexity. So which is it?

[karthicbz]

Hi, the space complexity for the second example is O(1). Since every time we iterate over the loop, we are reassigning the value to the same variables i and sum.

[Mark Skelton]

Hi, thanks for the great article. It explains space complexity very simply.

For the third example using recursion, I thought that the array[1...size] would create a new array for each method call which would add to the memory like: n + (n-1) + (n-2) + ... 1 = (n + 1) * (n / 2) (using the sum of n natural numbers formula) = O(n^2)

I suppose it depends on the implementation of the slice method but I think it returns a new array. If each method call does actually use O(1) space then overall O(n) is used as stated in the article. I am not sure that is the case here though...

[Mark Skelton]

Having continued with TOP I found this article with a section 'Copy on Write Optimization in Ruby Arrays'. For arrays of length 16 or larger, creating sub-arrays initially does not create a copy in memory! It only goes ahead and does that when it really has to (when writing to the new sub-array), maintaining the appearance of creating a new array for the user.

For the third example using recursion in this article, this means each function call uses O(1) auxiliary memory and thus O(n) for n recursive calls. So the space complexity (including the input array of length n) would be O(n) as stated in the article.

It just goes to show how you can only be really sure about space complexity when you know the programming language implementation.

[JackSoze]

Came here from the odin project course work...great piece, thanks!

[Tyler Hudson]

Great read, thank you for putting this together! I'm currently working through "The Odin Project" and your code examples/explanations really helped make these concepts stick for me.

[Alvin Kuria]

From the Odin

[Jamie Crosby]

I also found this via The Odin Project. Excellent article. Inspired me to join the dev.to community.

[S-yartey007]

It seems there is a bit of confusion when it comes to calculating the space complexity compared to the time complexity with regards to wether the input argument should be taken into account or not.

[Vladimir Laskin]

Brilliant article, thank you! Cleared up so many doubts I've had

[JackSoze]

This post is part of an assignment from the odin project course work...great piece, thanks!