DSA Space Complexity

Every program needs memory to run. Space complexity measures how much extra memory an algorithm uses as the input grows. Two programs can solve the same problem in the same time, yet one may need ten times more memory. Space complexity helps you spot that difference early.

Think about packing for a trip. One traveler carries a single small backpack. A friend brings a backpack and three suitcases for the same journey. Both reach the destination, but the friend needs far more room. Algorithms behave the same way with memory.

What Counts as Space

An algorithm uses space in two places.

• Input space holds the data given to the algorithm.
• Auxiliary space holds the extra data the algorithm creates while working, such as new lists, helper variables, and function calls waiting on the call stack.

Most discussions focus on auxiliary space because the problem fixes the input size. Total space equals input space plus auxiliary space.

Common Space Complexities

O(1) Constant Space

The algorithm uses the same small amount of memory no matter how large the input becomes. A running total is a good example. One variable stores the sum, whether the list has ten items or ten million.

def total(numbers):
    result = 0
    for n in numbers:
        result += n
    return result

O(n) Linear Space

Memory grows in step with the input. Copying a list into a new list doubles the data in memory.

def double_all(numbers):
    new_list = []
    for n in numbers:
        new_list.append(n * 2)
    return new_list

A list of 5 items creates 5 new slots. A list of 5,000 items creates 5,000 new slots.

O(n²) Quadratic Space

Memory grows with the square of the input. A grid that stores a value for every pair of items falls into this group.

def build_table(n):
    table = []
    for i in range(n):
        table.append([0] * n)
    return table

A table for 10 items holds 100 cells. A table for 1,000 items holds 1,000,000 cells.

Memory Growth at a Glance

Input size n = 4

O(1)   : [x]
O(n)   : [x][x][x][x]
O(n^2) : [x][x][x][x]
         [x][x][x][x]
         [x][x][x][x]
         [x][x][x][x]

Hidden Space in Recursion

Recursive functions consume memory even when they create no lists. Each call places a frame on the call stack, and the frame stays until the call finishes.

def countdown(n):
    if n == 0:
        return
    countdown(n - 1)

Calling countdown(3) stacks four frames before any call returns.

Call stack (top is newest)

| countdown(0) |
| countdown(1) |
| countdown(2) |
| countdown(3) |
----------------

The depth equals n, so this function uses O(n) space. A loop that does the same job uses O(1) space. Choosing a loop over recursion often saves memory.

Trading Space for Time

Many problems let you spend memory to gain speed. Computing Fibonacci numbers shows the idea clearly. The plain recursive version repeats the same work thousands of times. A dictionary that remembers earlier answers removes the repetition.

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

The memo dictionary adds O(n) space. In return, the running time drops from exponential to O(n). Programmers call this idea a space-time trade-off.

How to Calculate Space Complexity

• Ignore the input itself and count only the extra memory.
• Count each new list, dictionary, or set and note how its size depends on n.
• Add the maximum depth of recursive calls.
• Keep the largest term and drop constants, just as in Big O for time.

An algorithm that uses three variables and one list of size n has O(n) space. The three variables vanish because the list dominates.

In-Place Algorithms

An in-place algorithm changes the input directly and uses O(1) extra space. Reversing a list by swapping the first and last items works in place.

def reverse(items):
    left, right = 0, len(items) - 1
    while left < right:
        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1

Building a reversed copy would need O(n) space. The in-place version needs only two index variables.

Why Space Matters in Real Programs

Phones, tablets, and small devices carry limited memory. A program that wastes space can freeze an app or force the system to close it. Servers handle thousands of users at once, so a small waste per user multiplies into a large bill. Reading space complexity early lets you pick a design that fits the machine.

Key Points

• Space complexity measures extra memory as input size grows.
• Auxiliary space counts the memory an algorithm creates beyond the input.
• Recursive calls use stack memory equal to the recursion depth.
• O(1) means fixed memory, O(n) means memory grows with input, and O(n²) means memory grows with the square of the input.
• Extra memory can buy speed, as memoization shows.
• In-place algorithms save memory by changing the input directly.