How to Calculate Space Complexity in Python

With advancements in technology, the development of efficient algorithms has become imperative. The efficiency of an algorithm is measured based on its time complexity and space complexity.

In this tutorial, we will look at how to calculate Space Complexity in Python. Space Complexity is a measure of the amount of memory an algorithm needs to run to completion. It includes the memory needed to store the inputs, auxiliary space, and the output.

Step 1: Understanding Space Complexity

Space Complexity often refers to auxiliary space and it doesn’t include the space used by input data. It represents the amount of extra space the algorithm requires apart from the input data.

The total space required by a program is the sum of the auxiliary space and the space used by the input data. The space needed by input data is generally fixed, but auxiliary space varies with input data size, and hence space complexity is often equal to auxiliary space.

Step 2: Types of Space Complexity

Space Complexity varies based on the algorithm/program, and it’s categorized into the following types:

  1. Constant Space Complexity: An algorithm is said to have a constant space complexity when it requires a fixed amount of space for all input sizes. They are denoted as O(1).
  2. Linear Space Complexity: An algorithm is said to have a linear space complexity when the space required increases linearly with the input size. They are denoted as O(n).

Step 3: Calculating Space Complexity

Let’s understand this with an example. We’ll use an algorithm that computes the factorial of a number.

1
2
3
4
5
def factorial(n):
    if n==0:
        return 1
    else:
        return n*factorial(n-1)

Understanding the Code

In this code, the function factorial() is a recursive function that calculates the factorial of a number. It keeps calling itself until it reaches the base case of n==0.

In terms of space complexity: each recursive call to the function creates a new space in the stack memory. These function calls are added to the stack in reverse order of their occurrence. Hence, if the input number is ‘n’, then there would be ‘n’ recursive calls, and so the space complexity of this function becomes O(n).

Full Code

1
2
3
4
5
6
7
8
def factorial(n):
    if n == 0:
        return 1
    else:
        return n*factorial(n-1)
 
result = factorial(5)
print(result)

Output

120

Conclusion

Understanding and calculating space complexity is essential for writing efficient code. By being aware of how algorithms utilize resources, programmers can ensure that their applications are using system resources in the most efficient way possible. More often than not, you’ll have to find a balance between time and space complexity based on the specific requirements and constraints of your project.