DSA Interview Prep · Lesson

Space Complexity and Trade-offs

Measure auxiliary space for call stacks and auxiliary data structures, and recognise time-space trade-offs in memoisation and in-place algorithms.

What Does Space Complexity Measure?

Space complexity measures the extra memory beyond the input, called auxiliary space. A few variables is O(1); a result array or hash map is O(n). See the code.

# O(1) auxiliary space
def sum_array(nums):
    total = 0       # one integer variable
    for n in nums:
        total += n  # constant extra space
    return total

# O(n) auxiliary space
def copy_array(nums):
    return list(nums)  # allocates n slots

print(sum_array([1, 2, 3, 4]))  # 10
print(copy_array([1, 2, 3, 4]))  # [1, 2, 3, 4]

Call Stack Space in Recursion

Each recursive call adds a stack frame, so depth sets the space. Linear recursion is O(n); balanced tree DFS is O(log n). An iterative version can control this better.

import sys

def recursive_sum(n):
    if n == 0: return 0
    return n + recursive_sum(n - 1)
# Space: O(n) stack frames

def iterative_sum(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total
# Space: O(1)

print(recursive_sum(100))   # 5050
print(iterative_sum(100))   # 5050

All lessons in this course

← Back to DSA Interview Prep