Imagine you're packing for a trip. You could bring everything you own (uses lots of space), or pack only essentials (uses minimal space). Similarly, algorithms can use memory efficiently or wastefully.

Space complexity measures the amount of memory an algorithm needs as the input size grows.

Why Space Complexity Matters

Consider these scenarios:

Scenario 1: Mobile App

›Limited RAM (2-4 GB)
›Algorithm using O(n²) space might crash the app
›Algorithm using O(1) space runs smoothly

Scenario 2: Big Data Processing

›Processing millions of records
›O(n) extra space = Gigabytes of RAM needed
›O(log n) extra space = Minimal RAM needed

Scenario 3: Embedded Systems

›Microcontrollers with only 2 KB RAM
›Every byte counts
›Must use O(1) space algorithms

Key Idea: Space complexity measures how much extra memory an algorithm needs relative to input size.

Total Space vs Auxiliary Space

Total Space Complexity

Total space = Space for input + Space for auxiliary variables

Auxiliary Space Complexity

Auxiliary space = Extra space used by algorithm (excluding input)

Example:

Python

def sum_array(arr):
    total = 0                    # Extra variable: 1 unit
    for num in arr:              # No extra space
        total += num
    return total

# Input space: n (the array)
# Auxiliary space: O(1) (only 'total' variable)
# Total space: O(n) (input array + total variable)

Note: We usually focus on auxiliary space because input size is given and constant.

Understanding O(1) Space - Constant Space

Definition: Algorithm uses a fixed amount of extra memory, regardless of input size.

Example 1: Simple Variables

Python

def find_max(arr):
    max_val = arr[0]         # 1 variable
    
    for num in arr:
        if num > max_val:
            max_val = num    # Update same variable
    
    return max_val

# Extra space: 1 variable (max_val)
# Space Complexity: O(1)

Analysis:

›Input size: 10, 100, or 1,000,000 elements
›Extra variables: Always just 1 (max_val)
›Space Complexity: O(1)

Example 2: Swap Two Numbers

Python

def swap(a, b):
    temp = a         # 1 extra variable
    a = b
    b = temp
    return a, b

# Extra space: 1 variable (temp)
# Space Complexity: O(1)

Understanding O(n) Space - Linear Space

Definition: Extra memory grows proportionally with input size.

Example 1: Copy Array

Python

def copy_array(arr):
    new_arr = []             # New array
    
    for num in arr:
        new_arr.append(num)  # Add to new array
    
    return new_arr

# Input size: n
# Extra space: n (new array of same size)
# Space Complexity: O(n)

Example 2: Reverse Array

Python

def reverse_array(arr):
    reversed_arr = []        # New array
    
    for i in range(len(arr) - 1, -1, -1):
        reversed_arr.append(arr[i])
    
    return reversed_arr

# Input: [1, 2, 3, 4, 5]
# Output: [5, 4, 3, 2, 1]
# Extra space: n elements
# Space Complexity: O(n)

Better Approach: In-Place Reversal (O(1) Space)

Python

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

# Extra space: Only 2 variables (left, right)
# Space Complexity: O(1)

Comparison:

›First approach: O(n) space, creates new array
›Second approach: O(1) space, modifies original array
›Trade-off: Less space but modifies input

Understanding O(n²) Space - Quadratic Space

Definition: Extra memory grows with the square of input size.

Example: 2D Matrix

Python

def create_matrix(n):
    matrix = []
    
    for i in range(n):
        row = []
        for j in range(n):
            row.append(i * j)
        matrix.append(row)
    
    return matrix

# For n = 3:
# [[0, 0, 0],
#  [0, 1, 2],
#  [0, 2, 4]]
# 
# Space: n × n = n² elements
# Space Complexity: O(n²)

Recursion and Space Complexity

Recursive functions use extra space on the call stack.

Example 1: Factorial (O(n) Space)

Python

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

# factorial(5) calls:
# factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1)
# 
# Call stack depth: n
# Space Complexity: O(n) due to recursion stack

Example 2: Iterative Factorial (O(1) Space)

Python

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

# No recursion, no call stack
# Only one variable: result
# Space Complexity: O(1)

Comparison:

›Recursive: O(n) space (call stack)
›Iterative: O(1) space (just variables)

Common Space Complexities Compared

Space Complexity	Example	Memory for n=100	Memory for n=1000
O(1)	Finding max	Constant	Constant
O(log n)	Binary search (recursive)	~7 calls	~10 calls
O(n)	Copying array	100 units	1,000 units
O(n log n)	Merge sort	100 × 7	1,000 × 10
O(n²)	2D matrix	10,000 units	1,000,000 units

Space-Time Trade-offs

Sometimes we can trade space for time, or time for space.

Example: Fibonacci Sequence

Approach 1: Recursive (Slow, Less Space)

Python

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

# Time: O(2^n) - Very slow!
# Space: O(n) - Call stack depth

Approach 2: Memoization (Fast, More Space)

Python

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]

# Time: O(n) - Much faster!
# Space: O(n) - Store results in dictionary

Approach 3: Iterative (Fast, Minimal Space)

Python

def fibonacci_iterative(n):
    if n <= 1:
        return n
    
    prev2 = 0
    prev1 = 1
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

# Time: O(n) - Fast
# Space: O(1) - Minimal space!

Comparison:

Approach	Time	Space	Trade-off
Recursive	O(2^n)	O(n)	Slow, minimal space
Memoization	O(n)	O(n)	Fast, uses extra space
Iterative	O(n)	O(1)	Fast, minimal space - Best!

How to Calculate Space Complexity

Rule 1: Count Variables

Python

def example(n):
    a = 0           # 1 variable
    b = 0           # 1 variable
    c = 0           # 1 variable
    
    for i in range(n):
        print(a + b + c)

# Space: 3 variables + loop counter
# Space Complexity: O(1) - constant

Rule 2: Count Data Structures

Python

def example(n):
    arr = [0] * n      # Array of size n
    result = 0         # 1 variable
    
    for num in arr:
        result += num

# Space: n (array) + 1 (result)
# Space Complexity: O(n)

Rule 3: Count Recursion Depth

Python

def count_down(n):
    if n == 0:
        return
    print(n)
    count_down(n - 1)

# count_down(5) → count_down(4) → count_down(3) → ...
# Call stack: n levels deep
# Space Complexity: O(n)

Practice Problems

Problem 1: What's the Space Complexity?

Python

def mystery(arr):
    total = 0
    for i in range(len(arr)):
        for j in range(len(arr)):
            total += arr[i] * arr[j]
    return total

# Answer: O(1)
# Explanation: Only 'total' variable, loops don't create extra space

Problem 2: Reduce Space Complexity

Given this function, can you reduce its space complexity?

Python

# Original: O(n) space
def sum_first_k(arr, k):
    subset = arr[:k]  # Creates new array
    total = sum(subset)
    return total

# Improved: O(1) space
def sum_first_k_optimized(arr, k):
    total = 0
    for i in range(k):
        total += arr[i]
    return total

# No extra array needed!

Key Takeaways

Space Complexity measures extra memory used by an algorithm.

Auxiliary Space excludes input size (focus on extra variables/structures).

Common Complexities: O(1) < O(log n) < O(n) < O(n²)

Recursion uses O(depth) space for the call stack.

Trade-offs: Sometimes we use more space to get faster time.

In-place algorithms modify input directly to save space (O(1) instead of O(n)).

What's Next?

Now that you understand space complexity:

›Asymptotic Analysis - Deep dive into Big-O, Omega, Theta
›Array Operations - Apply complexity analysis to arrays
›Recursion - Master recursive space complexity

Practice Exercises

Determine the space complexity:

Exercise 1

Python

def exercise1(n):
    result = []
    for i in range(n):
        result.append(i * 2)
    return result

# Answer: O(n) - creates array of size n

Exercise 2

Python

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

# Answer: O(n) - recursion depth of n

Ready to continue? Let's explore Asymptotic Analysis next!

←

PreviousTime Complexity (Big-O)

NextAsymptotic Notation

→