Big O of Space Complexity

Interestingly, computer scientists use Big O notation to describe space complexity just as they do for time complexity.

Back when I introduced Big O notation in Chapter 3, , I described Big O in terms of what I called the “key question.” For time complexity, the key question was: if there are N data elements, how many steps will the algorithm take?

To use Big O for space complexity, we just need to reframe the key question. When it comes to memory consumption, the key question is: if there are N data elements, how many units of memory will the algorithm consume?

Here’s a simple example.

Let’s say we’re writing a function that accepts an array of strings and returns an array of those strings in ALL CAPS. For example, the function would accept an array like ["tuvi", "leah", "shaya", "rami", "yechiel"] and return ["TUVI", "LEAH", "SHAYA", "RAMI", "YECHIEL"]. Here’s one way we can write this function:

In this make_uppercase function, we accept an array. We then create a brand-new array called new_array and fill it with uppercase versions of each string from the original array.

By the time this function is complete, we’ll have two arrays floating around in our computer’s memory. We have the original array, which contains ["tuvi", "leah", "shaya", "rami", "yechiel"], and we have new_array, which contains ["TUVI", "LEAH", "SHAYA", "RAMI", "YECHIEL"].

When we analyze this function in terms of space complexity, we can see that this function creates a brand-new array that contains N elements. This is in addition to the original array which also holds N elements.

So let’s return to our key question: if there are N data elements, how many units of memory will the algorithm consume?

Because our function generated an additional N data elements (in the form of new_array), we’d say that this function has a space efficiency of O(N).

The way this appears on the following graph should look familiar:

Note that this graph is identical to the way we’ve depicted O(N) in graphs in previous chapters, with the exception that the vertical axis now represents memory consumed rather than time.

Now, let’s present an alternative make_uppercase function that is more memory-efficient:

In this second version, we don’t create any new arrays. Instead, we modify each value within the original array in place, replacing each string with an uppercase version of that string. We then return the modified array.

This is a drastic improvement in terms of memory consumption since our new function doesn’t consume any additional memory at all.

How do we describe this in terms of Big O notation?

Recall that with time complexity, an O(1) algorithm was one whose speed remained constant no matter how large the data. Similarly, with space complexity, O(1) means that the memory consumed by an algorithm is constant no matter how large the data.

Our revised make_uppercase function consumes a constant amount of additional space (zero!) no matter whether the original array contains four elements or one hundred. Because of this, this function is said to have a space efficiency of O(1).

It’s worth emphasizing that when using Big O to describe space complexity, we’re only counting the new data the algorithm is generating. Even our second make_uppercase function deals with N elements of data in the form of the array passed into the function. However, we’re not factoring those N elements into our Big O description, since the original array exists in any case, and we’re only focused on the extra space the algorithm consumes. This extra space is more formally known as auxiliary space.

However, it’s good to know that there are some references that include the original input when calculating the space complexity, and that’s fine. We’re not including it, and whenever you see space complexity described in another resource, you need to determine whether it’s including the original input.

Let’s now compare the two versions of make_uppercase in both time and space complexity:

Both versions are O(N) in time complexity, since they take N steps for N data elements. However, the second version is more memory-efficient, as it is O(1) in space complexity compared to the first version’s O(N).

It turns out that Version #2 is more efficient than Version #1 in terms of space while not sacrificing any speed, which is a nice win.