Algorithm Analysis: Space Complexity

In the previous article, we explored time complexity, which evaluates an algorithm’s efficiency by measuring how its runtime grows with input size. This article focuses on another critical concept: space complexity—a measure of the amount of memory an algorithm requires during execution.

What Is Space Complexity?

Space complexity quantifies the total memory space an algorithm consumes while running, typically denoted by the uppercase letter S. It consists of two main components:

1. Fixed (or Static) Component: This represents the baseline memory required for the algorithm’s execution—such as space for constants, simple variables, and input data—and remains constant regardless of input size.
2. Variable (or Dynamic) Component: This part scales with input size and includes memory used for recursion (e.g., call stack space) or dynamically allocated structures (e.g., arrays, hash tables).

Overall, space complexity is usually expressed as $S(n)$, where $n$ denotes the size of the input.

Example 1: Space Complexity of Simple Variables

Consider this simple function that computes the sum of two numbers:

def add(a, b):
    return a + b

Here, the space complexity is constant—$O(1)$—because only a fixed number of variables (a, b, and the return value) are used, irrespective of input magnitude.

Example 2: Space Complexity of Arrays

Now consider a function that sums all elements in a list:

def sum_list(nums):
    total = 0
    for num in nums:
        total += num
    return total

In this case, the input list nums has size $n$. Although total occupies constant space ($O(1)$), the list itself requires $O(n)$ space. Thus, the overall space complexity is $O(n)$.

Example 3: Space Complexity of Recursion

Recursive algorithms often consume more memory because each recursive call allocates space on the call stack. For instance, here’s a naive recursive implementation of the Fibonacci sequence:

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Each call to fibonacci pushes a new frame onto the stack. For input n, the maximum recursion depth reaches n, resulting in a space complexity of $O(n)$.

However, using dynamic programming, we can reduce the space complexity to $O(1)$:

def fibonacci_dynamic(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Here, only two variables (a and b) are used throughout, yielding constant-space complexity—$O(1)$—and significantly improved efficiency.

Summary

Space complexity is a vital dimension in algorithm analysis, helping us understand the memory resources an algorithm consumes at runtime. By analyzing and calculating space complexity, we can make more informed decisions when selecting algorithms under constrained memory conditions. Different implementations of the same problem may exhibit markedly different space complexities—an essential consideration during algorithm optimization.

In the next article, we’ll delve into Big O notation, the primary tool for expressing both time and space complexity. After studying this chapter, you’ll be equipped to evaluate algorithms more holistically—accounting for both runtime performance and memory footprint.