Introduction: Space Complexity

Alright; after having understood time complexity, this should be fairly easy.

We just learned that measuring time efficiency in terms of the absolute time it takes to run a code is not ideal. Similarly, we can't just say that the space complexity of a program is 73 bytes or 100 KB. This is because the absolute space required has more factors than just the code itself, the input size being one of them.

Let's get to the definition.

Space complexity measures how the memory/space required by an algorithm grows as the size of the input increases.

Let's take a trivial example where I give you 100 numbers individually, and you're to add them and tell me the final answer. You could go about it in multiple different ways, two of them being the following:

Algorithm 1

1. You keep writing down all the numbers I'm telling you in a notebook.
2. After I'm done, you add them using basic math and tell me the answer.

Algorithm 2

1. I give you the 1st number, you write it in the notebook.
2. Then, as soon as I give you the 2nd number, you write it, find the sum of 2 numbers running_sum and erase the two numbers.
3. Then, when I give you the 3rd number, you find the sum of running_sum and the 3rd number, write that and again erase everything else.
4. You keep on doing it until you've received all the 100 numbers.
5. The final value of running_sum is the desired output.

Okay, let's see if you yourselves can guess the space complexities of the abovementioned two algorithms.

So, as explained using the above explanations, I hope it's clear that although the time complexities of both algorithms will be the same, Algo 2 is better than Algo 1 in terms of Space Complexity.

While we've learned the basics of Space Complexity in this article, I want to call out that generally, if we have to choose between optimizing time and space, we usually prioritize optimizing time complexity.

This is because memory is more affordable nowadays, and time is often a more critical factor.