Analyzing Space Complexity

To determine the space complexity of a function or algorithm, start by identifying the variables and data structures used, including any additional space allocated dynamically. Analyze how these variables and structures grow with the input size. If the function uses recursion, consider both the maximum depth of recursion and the space used by each recursive call, as each adds a new frame to the call stack.

Example 1: Constant space

Consider a function that sums up the all integers from 0 to $n$:

Python
def func1(n):
    result = 0
    for i in range(n):
        result += i
    return result

This function uses a constant amount of extra space for the variable result and the loop counter i. The space does not depend on the size of the input $n$. Hence, the space complexity is $O(1)$, which is constant space.

Example 2: Linear space

Python
def func2(arr):
    result = []
    for item in arr:
        result.append(item)
    return result

This function creates a new list result that grows with the size of the input arr. The space used by result is proportional to the size of the input array, so the space complexity is $O(n)$, which is linear space.

Example 3: Recursive Function

Consider a recursive function that calculates the factorial of a number ( n ):

Python
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

This function calls itself recursively until it reaches the base case $n = 0$. Each recursive call adds a new frame to the call stack, which holds the current value of $n$ and waits for the result of factorial(n - 1). Since there are $n$ recursive calls in total, the maximum depth of the call stack is $n$, meaning the space complexity is $O(n)$, which is linear space.

Example 4: Dynamic Programming

Consider a dynamic programming approach to calculate the number of distinct subsequences between two strings s1 and s2:

Python
def distinct_subsequences(s1, s2):
    m, n = len(s1), len(s2)

    # This line dominates space complexity
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = 1

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[m][n]

In this function, a 2D table dp of size $(m + 1) \times (n + 1)$ is used, where m is the length of s1 and n is the length of s2. The table is used to store the results of subproblems to avoid redundant calculations. Since the size of the table grows with the product of the lengths of s1 and s2, the space complexity is $O(m \times n)$, which is quadratic space.

Test your knowledge

Question: What is the space complexity of func1?

Python
def func1(n):
    a = [0] * n
    b = [0] * n
    return a + b

Question: What is the space complexity of func2?

Python
def func2(n):
    result = []
    for i in range(n):
        result.append([0] * n)
    return result

Question: What is the space complexity of func3?

Python
def func3(arr):
    if len(arr) == 0:
        return
    func3(arr[1:])

Question: What is the space complexity of func4?

Python
def func4(n):
    if n <= 1:
        return
    func4(n//2)
    func4(n//2)