Start learning free

LESSON 211 OF 410 · BIG O NOTATION

Space Complexity in Python: Understanding and Computing

Reading Read the full explanation

Space Complexity measures the total amount of memory that an algorithm or operation needs to run according to its input size.

Space Complexity is a parallel concept to Time Complexity. We express space complexity measurements using the Big-O notation, following the same guidelines like we do for time complexity.

Now let's learn how to compute space complexity by taking a few examples (written in pseudo-code, so they apply to any language):

Constant Space Complexity:

function add(a, b):
    sum = a + b
    return sum

In the example above, we use 3 number variables: a and b, which are input variables and sum, which is an auxiliary variable.

And because the space requirement is fixed (3 number variables), hence it is called Constant Space Complexity and is noted with O(1).

Linear Space Complexity:

function generate(n):
    numbers = empty list
    for i from 0 to n - 1:
        add i to the end of numbers
    return numbers

In the example above, we use an auxiliary list numbers which is populated with n numbers.

Since the total space requirement is n numbers, the Space Complexity is increasing linearly with the increase in the input value n, hence it is called as Linear Space Complexity and is noted with O(n).

Quadratic Space Complexity:

function generate(n):
    numbers = empty list
    for i from 0 to n - 1:
        add an empty list to the end of numbers
        for j from 0 to n - 1:
            add j to the end of the row at index i
    return numbers

In the example above, we use an auxiliary 2D list numbers of n rows and n columns.

Since the total space requirement is n^2 numbers, the Space Complexity is directly proportional to the squared of the input value n, hence it is called as Quadratic Space Complexity and is noted with O(n^2).

Extra/Auxiliary Space:

Sometimes Extra/Auxiliary Space is confused with Space Complexity. But Auxiliary Space is the extra space or the temporary space used by the algorithm during its execution (without taking the input values into account).

Space Complexity = Auxiliary Space + Input space

Let's see some examples:

function addAll(arr):
    sum = 0
    for each num in arr:
        sum += num
    return sum

In the example above, we have an input list arr. If we denote its length by n, the Input Space is O(n).

However, we use only 2 auxiliary variables sum and num, so the Extra Space is O(1).

Next lesson

PYTHON · BIG O NOTATION

Space Complexity in Python, explained

Understanding the Problem

The core challenge of understanding space complexity lies in recognizing how much memory an algorithm uses relative to its input size. This is crucial in scenarios where memory is a limited resource, such as in embedded systems or large-scale data processing.

Common applications include optimizing algorithms for better performance and ensuring that programs run efficiently on devices with limited memory.

Potential pitfalls include confusing space complexity with time complexity and not accounting for all memory usage, such as temporary variables or recursive call stacks.

Approach

To solve problems related to space complexity, follow these steps:

  1. Identify the input size and the variables used.
  2. Determine the memory required for input storage.
  3. Calculate the memory used by auxiliary variables and data structures.
  4. Sum the input space and auxiliary space to get the total space complexity.

Let's discuss a naive solution and its limitations:

Consider a function that sums the elements of an array:

def sum(arr):
    total = 0
    for num in arr:
        total += num
    return total

This function has a space complexity of O(n) due to the input array, but the auxiliary space is O(1). This is efficient, but if we were to use additional data structures, the space complexity could increase.

Algorithm

Let's break down the algorithm for calculating space complexity:

  1. Identify the input variables and their sizes.
  2. Identify any auxiliary variables and data structures.
  3. Calculate the total memory used by input and auxiliary variables.
  4. Express the total memory usage in Big-O notation.

Code Implementation

Here is the Python code for the examples discussed:

# Constant Space Complexity: O(1)
def sum(a, b):
    sum = a + b
    return sum

# Linear Space Complexity: O(n)
def generate(n):
    numbers = []
    for i in range(n):
        numbers.append(i)
    return numbers

# Quadratic Space Complexity: O(n^2)
def generate(n):
    numbers = []
    for i in range(n):
        numbers.append([])
        for j in range(n):
            numbers[i].append(j)
    return numbers

# Example of Extra/Auxiliary Space: O(1)
def sum(arr):
    total = 0
    for num in arr:
        total += num
    return total

Complexity Analysis

Let's analyze the time and space complexity of each approach:

  • Constant Space Complexity: O(1) - Fixed memory usage regardless of input size.
  • Linear Space Complexity: O(n) - Memory usage grows linearly with input size.
  • Quadratic Space Complexity: O(n^2) - Memory usage grows quadratically with input size.
  • Extra/Auxiliary Space: O(1) - Fixed additional memory usage.

Comparing these complexities helps us understand the trade-offs between different solutions. For example, a quadratic space complexity algorithm may be less efficient than a linear one for large inputs.

Edge Cases

Identifying potential edge cases is crucial for robust algorithms:

  • Empty input (e.g., an empty array).
  • Very large input sizes.
  • Special values (e.g., negative numbers, zeros).

For example, testing the sum function with an empty array should return 0:

print(sum([]))  # Output: 0

Testing

To test the solution comprehensively, use a variety of test cases:

  • Simple cases (e.g., small arrays).
  • Complex cases (e.g., large arrays, nested structures).
  • Edge cases (e.g., empty arrays, special values).

Using testing frameworks like unittest or pytest can help automate and organize tests.

Thinking and Problem-Solving Tips

Here are some tips for approaching and solving such problems:

  • Break down the problem into smaller parts.
  • Understand the input and output requirements.
  • Consider different approaches and their trade-offs.
  • Practice solving similar problems to improve your skills.

Conclusion

Understanding space complexity is crucial for writing efficient algorithms. By analyzing and optimizing space complexity, we can ensure that our programs run efficiently, especially in memory-constrained environments.

Practice and exploration are key to mastering these concepts. Keep solving problems and studying algorithms to improve your skills.

Additional Resources

For further reading and practice, consider the following resources:

Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free