Space Complexity: How Much Memory Does It Use?

After Completing This Topic

You'll understand what space complexity is, how it relates to time complexity, and when you need to be mindful of memory usage in practice.

I Thought Only Speed Matters

When evaluating algorithms, it's easy to focus solely on "how fast" it is. We compare O(n), O(n log n), and O(n^2) using Big-O notation to determine time complexity.

However, computers aren't just CPUs. They also have memory (RAM). Even the fastest algorithm won't run on a typical computer if it uses 100GB of memory.

Space complexity is the analysis of how much memory an algorithm uses as the input size grows. It uses the same Big-O notation as time complexity.

O(1) – Constant Space, Independent of Input

def find_max(arr):
    result = arr[0]
    for x in arr:
        if x > result:
            result = x
    return result

Whether the array has 100 elements or 1 million, the additional variable used is just result. The space complexity is O(1). This is called "constant space."

O(n) – Memory Proportional to Input

def get_squares(arr):
    result = []
    for x in arr:
        result.append(x * x)
    return result

It creates a new array with the same size as the input array. If the input has n elements, it uses n additional memory. The space complexity is O(n).

def reverse_string(s):
    return s[::-1]

This is also O(n) because it creates a new string with the same length as the original.

O(n^2) – Two-Dimensional Structure

def create_matrix(n):
    return [[0] * n for _ in range(n)]

Creating an n×n matrix results in a space complexity of O(n^2). Adjacency matrices are a typical example.

The Hidden Space of Recursion

Each time a recursive function is called, it stacks a frame on the call stack. This also consumes memory.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Calling factorial(1000) will stack 1000 frames on the call stack. The space complexity is O(n). In Python, the default recursion depth is limited to 1000, and exceeding this will raise a RecursionError.

It can be reduced to O(1) by using a loop:

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

It produces the same result but doesn't use the stack. As shown, converting recursion to a loop can save space.

Time and Space Trade-offs

"Saving time often requires more space, and saving space often requires more time." This is called the time-space trade-off.

A typical example is caching:

# Space O(1), Time O(n) – Calculates every time
def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Space O(n), Time O(1) lookup – Pre-calculates and stores
cache = {}
def fib_cached(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        result = n
    else:
        result = fib_cached(n - 1) + fib_cached(n - 2)
    cache[n] = result
    return result

More memory is used, but the same value is not calculated twice. This trade-off is the core of dynamic programming (DP).

Hash tables are the same. Sorting an array and using binary search has a space complexity of O(1), but creating a hash table uses an additional space complexity of O(n) while speeding up lookups to O(1).

When Space Becomes a Problem in Practice

In typical web development, you don't often need to worry about space complexity because there is enough RAM. However, memory becomes a bottleneck in the following situations:

Processing Large Amounts of Data: When analyzing a 10GB log file, loading it all into memory will cause it to crash. It needs to be processed line by line (streaming).

Mobile/Embedded: Smartphones and IoT devices have limited RAM. Algorithms need to be designed to use less memory.

Coding Tests: Problems may have conditions like "Memory Limit: 256MB." A solution with O(n^2) space complexity may fail due to exceeding the memory limit.

Key Takeaways

Space complexity is the analysis of how much memory an algorithm uses as the input size grows. The call stack of recursion also consumes space. Converting recursion to a loop can reduce O(n) to O(1). Time and space are in a trade-off relationship, and you need to decide which to prioritize based on the situation.