The Self-Taught Computer Scientist

Introduction to Algorithms
16
is the amount of memory your program requires, and data structure space is the amount of memory 
your program needs to store the data set, for example, the size of a list you are searching. The amount 
of memory your algorithm uses to hold this data depends on the amount of input the problem requires. 
Temporary space is the amount of memory your algorithm needs for intermediary processing, for 
example, if your algorithm needs to temporarily copy a list to transfer data.
You can apply the time complexity concepts you learned earlier to space complexity. For example, 
you can calculate a factorial of 
n (a product of all positive integers less than or equal to n) using an 
algorithm that has a constant, O(1), space complexity:
x = 1
n = 5
for i in range(1, n + 1):
x = x * i
The space complexity is constant because the amount of space your algorithm needs does not grow 
as 
n gets larger. If you decided to store all the factorials up to n in a list, your algorithm would have a 
linear space complexity, O(
n):
x = 1
n = 5
a_list = []
for i in range(1, n + 1):
a_list.append(x)
x = x * i
Your algorithm’s space complexity is O(
n) because the amount of space it uses grows at the same 
pace as 
n.
Like with time complexity, the acceptable level of space complexity for an algorithm depends on 
the situation. In general, though, the less space an algorithm requires, the better.
Why Is This Important?
As a computer scientist, you need to understand the different orders of magnitude to optimize your 
algorithms. When you are trying to improve an algorithm, you should focus on changing its order of 
magnitude instead of improving it in other ways. For example, say you have an O(
n**2) algorithm that 
uses two 
for
loops. Instead of optimizing what happens inside your loops, it is much more important 
to determine whether you can rewrite your algorithm so that it doesn’t have two nested 
for
loops and 
thus has a smaller order of magnitude.
If you can solve the problem by writing an algorithm with two unnested 
for
loops, your algorithm 
will be O(
n), which will make a massive difference in its performance. That change will make a much 
bigger difference in your algorithm’s performance than any efficiency gains you could get by tweaking 
your O(
n**2) algorithm. However, it is also important to think about best- and worst- case scenarios 

---