Space Complexity — Big O & Complexity Analysis | Sabaoon Academy

Space complexity measures how much memory an algorithm needs as input size grows. It uses the same Big O notation as time complexity and is just as important — especially when working with large datasets, embedded systems, or memory-constrained environments.

What Counts as Space

Space complexity typically refers to auxiliary space — the extra memory your algorithm allocates beyond the input itself. The input is already in memory; we measure what else your algorithm needs.

For example, if you have a list of n items and your algorithm creates another list of n items to work with, that is O(n) auxiliary space.

O(1) — Constant Space

An algorithm uses O(1) space if it allocates a fixed number of variables regardless of input size.

def find_max(nums):
    max_val = nums[0]    # one variable
    for n in nums:
        if n > max_val:
            max_val = n  # reuses the same variable
    return max_val

No matter how large nums is, this function only ever uses one extra variable (max_val). That is O(1) space.

def reverse_in_place(arr):
    left, right = 0, len(arr) - 1    # two variables
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

This reverses the list by modifying it directly (in-place) — O(1) space. Compare that to:

def reverse_copy(arr):
    return arr[::-1]   # creates a new list of size n — O(n) space

Same result, different memory cost.

O(n) — Linear Space

An algorithm uses O(n) space when it allocates memory proportional to the input size.

def find_duplicates(nums):
    seen = set()         # grows with input — O(n) space
    duplicates = []
    for n in nums:
        if n in seen:
            duplicates.append(n)
        seen.add(n)
    return duplicates

The seen set can grow to hold up to n elements. This is a classic time-space tradeoff: by spending O(n) extra memory on a hash set, we bring the time complexity from O(n²) (nested loops) down to O(n).

Merge sort also uses O(n) space because of the temporary arrays created during merging:

def merge(left, right):
    result = []           # up to n elements allocated
    ...

O(log n) — Logarithmic Space

Recursive algorithms often use O(log n) space for the call stack when the recursion depth is logarithmic.

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

The recursion depth is at most log₂(n) — so the call stack uses O(log n) space. The iterative version uses O(1) space.

O(n) Stack Space from Recursion

Recursion uses stack space equal to the maximum depth of the call stack.

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)   # depth = n frames on the stack

For factorial(1000), there are 1,000 frames on the stack — O(n) space. For large n, this causes a stack overflow in many languages.

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

The memoisation dictionary uses O(n) space, and the call stack at any point uses O(n) depth — total O(n) space, but time drops from O(2ⁿ) to O(n).

The Time-Space Tradeoff

Most optimisations in algorithms involve trading one resource for another. The common patterns:

Situation	Trade
Replace nested loops with a hash set	More space (O(n)), less time (O(n²) → O(n))
Cache recursive results (memoisation)	More space (O(n)), less time (O(2ⁿ) → O(n))
Use in-place sort instead of merge sort	Less space (O(1) → O(n)), same or worse time
Precompute and store prefix sums	More space (O(n)), faster range queries (O(n) → O(1))

Neither time nor space is always the priority. Know which one is scarce in your context.

How to Calculate Space Complexity

Ask these questions as you read code:

What data structures are allocated? Arrays, sets, dictionaries, trees — how large can they grow relative to n?
Is there recursion? If yes, how deep can the call stack go?
Are copies being made? Slicing an array creates a copy — that is O(k) space for a slice of length k.

def count_chars(s):
    freq = {}           # at most 26 entries for lowercase letters → O(1)
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    return freq

Even though s can be arbitrarily long, the dictionary only has as many entries as there are distinct characters. If the alphabet is bounded (e.g., lowercase ASCII = 26 chars), this is O(1) space, not O(n).

Key Takeaways

Space complexity measures auxiliary memory — what your algorithm allocates beyond the input.
O(1) space: a fixed number of variables; O(n) space: data structures that grow with input; O(log n) space: typical recursive call stacks.
Recursion depth contributes to space complexity through the call stack.
Most algorithmic optimisations involve a time-space tradeoff — know which resource matters in your context.
A bounded alphabet or value range can turn what looks like O(n) space into O(1).