Space Complexity

Introduction

Understanding how much memory an algorithm needs is just as important as understanding how much time it takes.

An algorithm can be extremely fast but still unusable if it consumes too much memory.

For example, imagine processing one million numbers. You could process them one at a time using almost no additional memory, or create another array containing all one million results. Both approaches may produce the same answer, but their memory requirements are very different.

That is what space complexity helps us measure.

Why Do We Care About Space?

Computers have a limited amount of memory.

When an algorithm runs, it needs memory for things such as:

• Variables
• Arrays and other data structures
• Temporary values
• Function calls
• Recursion
• Objects created during execution

As the input becomes larger, the amount of memory required by an algorithm may also increase.

Consider these two approaches:

# Approach 1total = 0 for number in numbers:    total += number

The algorithm processes each number and keeps only the running total.

Now compare it with:

# Approach 2squares = [] for number in numbers:    squares.append(number * number)

The second approach creates a new collection whose size grows with the input.

The difference is not primarily about what they calculate.

It is about how much additional memory they need while doing it.

What Is Space Complexity?

Just like time complexity, we usually express space complexity using Big O notation.

If an algorithm needs roughly the same amount of extra memory regardless of the input size, its space complexity is:

O(1)

If the extra memory grows proportionally with the input:

O(n)

The goal is not to calculate the exact number of bytes used by the program.

Instead, we focus on how memory usage scales.

What Uses Memory?

When an algorithm runs, memory can be needed for several reasons.

Variables

Simple variables usually require a fixed amount of memory.

count = 0maximum = 100found = False

Regardless of whether the input contains 10 elements or 10 million elements, these variables do not grow with the input.

So the additional space is:

O(1)

Data Structures

A data structure can require memory proportional to the input.

copy = [] for number in numbers:    copy.append(number)

If numbers contains n elements, copy also contains n elements.

Therefore:

Space = O(n)

Function Calls

Every function call requires some memory to keep track of things such as:

• Parameters
• Local variables
• Where execution should return

This becomes particularly important with recursion.

Auxiliary Space vs Input Space

This distinction is important when discussing space complexity.

Suppose an algorithm receives an array containing n elements.

That input array already exists. The algorithm does not necessarily create it.

Now imagine the algorithm creates another array of n elements.

There are two different things to consider:

Input space Memory occupied by the input itself.

Auxiliary space Additional memory used by the algorithm beyond the input.

For example:

def double_values(numbers):    result = []     for number in numbers:        result.append(number * 2)     return result

The input numbers requires O(n) space.

The new result array also requires O(n) additional space.

So the algorithm uses:

• Input space: O(n)
• Auxiliary space: O(n)

When interviewers ask for the space complexity of an algorithm, they often focus on the auxiliary space unless they explicitly say to include the input.

Constant Space: O(1)

An algorithm uses constant extra space when the amount of additional memory does not grow with the input size.

def find_max(numbers):    maximum = numbers[0]     for number in numbers:        if number > maximum:            maximum = number     return maximum

The algorithm scans all n elements, but it only maintains one extra variable: maximum.

It does not create another array.

Therefore:

• Time: O(n)
• Auxiliary space: O(1)

This is an important idea:

An algorithm can take O(n) time while using only O(1) extra space.

Time and space measure different resources.

Linear Space: O(n)

Extra memory is linear when it grows proportionally with the input.

def create_copy(numbers):    result = []     for number in numbers:        result.append(number)     return result

For n input elements, the algorithm creates n new elements.

Therefore:

Auxiliary space = O(n)

It does not matter whether the new array contains the original values, transformed values, or some other information. If the amount of additional storage grows with n, the auxiliary space is O(n).

Quadratic Space: O(n²)

Sometimes an algorithm creates a structure whose size grows with the square of the input.

For example, an n × n matrix:

matrix = [] for i in range(n):    row = []     for j in range(n):        row.append(0)     matrix.append(row)

There are n rows and each row contains n elements.

So the total number of stored elements is:

n × n = n²

Therefore:

Space = O(n²)

This can become expensive very quickly as n increases.

What About Loops?

A common mistake is to assume that nested loops automatically mean large space complexity.

They do not.

Consider:

for i in range(n):    for j in range(n):        print(i, j)

The nested loops execute n² times.

But the algorithm does not create n² pieces of stored data. It only uses the loop variables.

Therefore:

• Time: O(n²)
• Space: O(1)

Number of operations and amount of stored memory are different things.

Recursion and the Call Stack

Recursion requires special attention because every active function call needs memory.

Consider:

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

If n = 5, the calls look like:

countdown(5)    ↓countdown(4)    ↓countdown(3)    ↓countdown(2)    ↓countdown(1)    ↓countdown(0)

Before the first call can finish, all of these calls remain active.

There are n active calls.

Therefore:

Auxiliary space = O(n)

This memory comes from the call stack.

In-Place Algorithms

An algorithm is often called in-place when it performs its work using only a small amount of additional memory rather than creating another data structure proportional to the input.

For example:

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

The array itself is modified.

Only a few variables are used:

• left
• right
• temporary storage involved in swapping

So the auxiliary space is:

O(1)

This is often valuable when memory is limited.

Time and Space Trade-offs

Sometimes you can make an algorithm faster by using more memory.

Consider searching for repeated values.

One approach repeatedly scans the data.

Another approach stores previously seen values in a set:

def has_duplicate(numbers):    seen = set()     for number in numbers:        if number in seen:            return True         seen.add(number)     return False

The set requires additional memory, but it can make lookups much faster.

This illustrates a fundamental idea:

More memory can sometimes buy less execution time.

There is no universally best choice. The right solution depends on the constraints.

How to Analyze Space Complexity

When analyzing an algorithm, ask three questions:

1. What memory grows with the input?

Look for:

• Arrays
• Lists
• Hash tables
• Trees
• Matrices
• Other dynamically growing structures

2. How many elements can exist at the same time?

Creating n elements one after another is different from keeping all n elements in memory simultaneously.

We care about the maximum memory occupied at once.

3. Does recursion increase the call stack?

Count the maximum number of simultaneously active recursive calls.

Then simplify the result using Big O.

For example:

5 variables       → O(1)n extra elements  → O(n)n × n matrix      → O(n²)n recursive calls → O(n)

A Common Trap: Sequential vs Simultaneous Memory

Consider:

for i in range(n):    temp = [0] * n    process(temp)

The list temp contains n elements, so at some point the algorithm needs O(n) additional memory.

Now imagine creating two arrays:

array A → n elementsarray B → n elements

The total is 2n.

But Big O ignores constant factors:

O(2n) = O(n)

The important question is how the memory grows, not the exact number of variables or bytes.

Common Mistakes

Quick Check

def find_max(numbers):    maximum = numbers[0]     for number in numbers:        if number > maximum:            maximum = number     return maximum

Quick Recap

• Space complexity describes how an algorithm's memory requirement grows with input size.
• Auxiliary space is the additional memory used by the algorithm.
• O(1) means constant extra memory.
• O(n) means memory grows linearly with the input.
• O(n²) commonly appears when storing an n × n structure.
• Nested loops affect time, not necessarily space.
• Recursion uses the call stack and can increase space complexity.
• In-place algorithms aim to use very little additional memory.
• Sometimes using more memory can make an algorithm faster.

Where This Leads

You now know how to analyze the two main resources an algorithm consumes:

Time → How does the amount of work grow?

Space → How does the amount of memory grow?

There is one important question left:

What happens when an algorithm temporarily uses more memory during an operation, but does not keep it permanently?

That leads to Amortized Analysis, the final chapter of the Complexity section.