Introduction

When analyzing an algorithm, we are interested in more than just how quickly it runs. We also need to understand how much memory it requires while processing the input. As the input size increases, the amount of memory required by an algorithm may also increase. Space complexity provides a way to describe this growth and helps us understand how efficiently an algorithm uses memory.
For example, one algorithm may process a list using only a few variables, while another may create a new list containing every element of the input. Both algorithms may process the same input, but their additional memory requirements can be very different.
In this article, we will learn what space complexity means, understand the difference between space complexity and auxiliary space, calculate space complexity step by step, analyze common space complexities such as O(1), O(n), O(n²), and O(log n), and understand how recursion affects memory usage.

Table of Contents

---

What Is Space Complexity?

Space complexity describes how the memory requirements of an algorithm grow as the size of its input increases.
The input size is usually represented by n. Instead of measuring memory in exact megabytes, space complexity describes how memory usage grows in relation to n.
For example, consider an algorithm that creates a new list containing one element for every input element:

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

If numbers contains n elements, result can also contain n elements. Therefore, the additional memory created by the algorithm grows linearly with the input size.

Auxiliary Space: O(n)

Space complexity is therefore concerned with the growth of memory usage, rather than the exact amount of memory used by a particular computer.
When analyzing an algorithm, memory can be required for variables, arrays, lists, strings, objects, temporary data structures, and recursive function calls.

Space Complexity vs. Auxiliary Space

The terms space complexity and auxiliary space are closely related, but it is important to understand what memory is being counted.
The main distinction is whether the memory required to store the input is included in the analysis.

• Space complexity: Describes how the total memory requirement of an algorithm grows with the input size. It may include the memory required for the input and the additional memory used during execution.
• Auxiliary space: Describes only the additional memory used by the algorithm apart from the input.
• Input Space: The memory required to store the data provided to the algorithm.

Consider the following example:

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

Suppose numbers contains n elements. The list itself is the input and therefore requires memory proportional to n.

Input Space: O(n)

The algorithm does not create another list, array, or data structure proportional to n. It only uses a fixed number of additional variables.

Auxiliary Space: O(1)

If we consider both the input and the additional memory, the total memory requirement can be represented as:

O(n) + O(1) = O(n)

Therefore:

Total Space: O(n)

This example shows why the distinction matters. The algorithm has O(n) total space when the input is included, but it uses only O(1) auxiliary space.
Now consider an algorithm that creates a second list:

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

The input list contains n elements, so its input space is O(n). The newly created result list can also contain n elements, so the algorithm uses O(n) additional memory.

Input Space: O(n)

Auxiliary Space: O(n)

The total space is therefore:

O(n) + O(n) = O(2n) = O(n)

Notice that both algorithms can have O(n) total space when the input is included, but their auxiliary-space requirements are different.

Term	Meaning	Example
Input Space	Memory required to store the input	List of n elements: O(n)
Auxiliary Space	Additional memory created by the algorithm	Fixed variables: O(1)
Total Space	Input space plus additional memory	O(n) + O(1) = O(n)

Why Auxiliary Space Is Important: Auxiliary space is particularly useful when comparing algorithms because it shows how much extra memory an algorithm requires beyond the data it was given.
For example, an in-place algorithm may process an input list using O(1) auxiliary space, while another algorithm may create another list of n elements and use O(n) auxiliary space.
Both algorithms receive the same input, but the second algorithm requires substantially more additional memory.

In simple terms:

• Input Space: Memory used to store the input.
• Auxiliary Space: Extra memory used by the algorithm.
• Total Space: Input space plus auxiliary space.

How to Calculate Space Complexity: Step-by-Step

To calculate space complexity, examine the memory used by the algorithm and determine how that memory changes as the input size increases.

1. Identify the Input Size: Determine what represents n. It may be the number of elements in a list, the length of a string, or the dimensions of a matrix.
2. Identify the Input Data: Determine how much memory is already required to store the input. Keep this separate if you are calculating auxiliary space.
3.  Identify Variables: Check the variables created by the algorithm. A fixed number of variables generally requires O(1) additional space.
4. Identify Additional Data Structures: Look for newly created lists, arrays, strings, dictionaries, matrices, objects, or other structures.
5.  Determine How Their Size Changes: Ask whether the amount of stored data remains constant or grows with n.
6.  Analyze Temporary Storage: Include temporary data structures if they contribute to the maximum memory used during execution.
7.  Analyze Recursive Calls: If recursion is used, determine the maximum number of active function calls stored on the call stack.
8. Find Maximum Simultaneous Memory: Space complexity depends on the maximum amount of memory required at any one time.
9. Simplify the Expression: Ignore constant factors and lower-order terms and keep the dominant growth term.

For example, suppose an algorithm creates a list of n elements and also uses a fixed number of variables:

O(n) + O(1) = O(n)

The dominant term is O(n), so the auxiliary space complexity is O(n).

Common Space Complexity Examples

Different algorithms require different amounts of additional memory. Four common space-complexity patterns are O(1), O(log n), O(n), and O(n²).

1.O(1): Constant Space

An algorithm uses constant auxiliary space when the amount of additional memory remains fixed regardless of the input size.

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

The algorithm uses only a fixed number of additional variables. Whether the array contains 10 elements or 10 million elements, the number of variables remains the same.

Auxiliary Space: O(1)

The loop increases the amount of work performed, but it does not increase auxiliary space because the same variables are reused.

2.O(n): Linear Space

An algorithm requires linear space when the amount of additional memory grows proportionally with the input size.

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

If numbers contains n elements, result can also contain n elements.

Auxiliary Space: O(n)

The amount of additional memory grows at the same rate as the input size.

3.O(n²): Quadratic Space

Quadratic space can occur when an algorithm creates a two-dimensional structure containing n rows and n elements in each row.

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

The matrix contains n rows, and every row contains n elements.

n × n = n²

Therefore:

Auxiliary Space: O(n²)

4.O(log n): Logarithmic Space

Logarithmic auxiliary space can occur when the amount of stored information grows logarithmically with the input size. A common example is a recursive algorithm that reduces the problem size by a constant factor at every step.

def divide(n):
    if n <= 1:
        return
    divide(n // 2)

The input size is reduced approximately as follows:

n to n/2  to  n/4 and so on

The maximum recursion depth is approximately log n.

Auxiliary Space: O(log n)

It is important to understand that a loop performing log n iterations does not automatically use O(log n) space. If the loop reuses a fixed number of variables, its auxiliary space can remain O(1).

Loop Without Additional Storage:

for number in numbers:
    square = number * number
    print(square)

The variable square is reused during every iteration.

Auxiliary Space: O(1)

Loop With Additional Storage:

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

Each iteration adds another value to squares. If there are n input elements, the new list can contain n elements.

Auxiliary Space: O(n)

How to Calculate Space Complexity in Recursion

Recursive algorithms require additional memory because each active function call is stored on the call stack.
When calculating recursive space complexity, the most important question is: What is the maximum number of recursive calls that are active at the same time?
Consider the following example:

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

The recursive calls form a chain:

countdown(n) to countdown(n - 1) to countdown(n - 2) and so 

Before the base case is reached, approximately n function calls can be active on the stack.

Auxiliary Space: O(n)

Maximum Recursion Depth: The maximum recursion depth is the deepest level reached by the recursive calls. This determines how many function-call frames can exist simultaneously.

Logarithmic Recursion: If every recursive call reduces the problem size by a constant factor, such as dividing it by 2, the recursion depth can be O(log n).

def search(n):
    if n <= 1:
        return
    search(n // 2)

The input sizes decrease approximately as:

n to n/2 to n/4 to n/8  and so on

Therefore, the recursion stack has logarithmic depth.

Auxiliary Space: O(log n)

Multiple Recursive Calls: Multiple recursive calls do not automatically mean exponential space. They may cause a large number of total calls, increasing time complexity, while the maximum number of simultaneously active calls remains much smaller.

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

The total number of calls grows rapidly, but the maximum recursion depth is n.

Auxiliary Space: O(n)

This demonstrates an important distinction: time complexity considers the total computational work, while recursive space complexity considers the maximum number of active calls on the stack.

Recursion With Additional Data: If each recursive call creates additional data, both the call stack and that data must be considered.

def process(n):
    if n == 0:
        return
    temporary = [0] * n
    process(n - 1)

Here, the analysis must consider the memory used by the active recursive calls as well as the temporary data created during those calls.
Each active recursive call creates a list whose size depends on n. At the deepest point, the lists contain approximately n, n - 1, n - 2, and so on elements.
These lists remain allocated while the deeper recursive calls are active, so their memory requirements accumulate.

n + (n - 1) + (n - 2) + ... + 1 = O(n²)

Therefore, the auxiliary space for this example is O(n²).

Therefore, recursive space analysis should consider:

• The maximum recursion depth.
• The memory used by each active call.
• Any additional data structures created during recursion.

In-Place Algorithms: An in-place algorithm performs its operation using a small amount of additional memory. It modifies the input data directly instead of creating another data structure of proportional size.

Example: The following function reverses a list in place by swapping elements from both ends. It does not create another list, so the auxiliary space is O(1).

def reverse_list(arr):
    left = 0
    right = len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
numbers = [1, 2, 3, 4, 5]
reverse_list(numbers)
print(numbers)

Output:

[5, 4, 3, 2, 1]

The list is modified directly, and only a few variables are used regardless of the input size. Therefore, the auxiliary space is O(1).

Common Mistakes to Avoid

1. Assuming every loop uses O(n) space: A loop may execute n times while using only O(1) auxiliary space if it reuses the same variables.
2. Confusing time and space complexity: Repeating an operation n times affects time complexity, but it does not automatically mean that n pieces of memory are stored.
3. Ignoring the recursion stack: Every active recursive function call requires memory on the call stack.
4. Counting every recursive call as simultaneous memory: Space depends on the maximum number of active calls at one time, not simply the total number of calls made during the entire execution.
5. Ignoring temporary data: Temporary lists, arrays, strings, and objects can contribute to the maximum memory used by the algorithm.
6. Confusing input space with auxiliary space: Always determine whether the analysis includes the input itself or only the additional memory created by the algorithm.
7. Assuming multiple recursive calls mean exponential space: Multiple recursive calls can produce exponential time complexity while the recursion depth remains linear.
8. Assuming an in-place algorithm uses no memory: An in-place algorithm can still use a fixed amount of additional memory for variables and temporary values. It simply avoids creating additional storage proportional to the input size.

Space Complexity Cheat Sheet

The following table provides a quick reference for common space-complexity patterns.

Pattern	Typical Auxiliary Space	Explanation
Fixed number of variables	O(1)	The amount of additional memory remains constant.
Logarithmic recursion depth	O(log n)	The recursion stack grows logarithmically.
New list containing n elements	O(n)	Additional storage grows linearly.
Linear recursion depth	O(n)	Up to n function calls can be active.
New n × n matrix	O(n2)	The structure contains n2 elements.
In-place processing with fixed variables	O(1)	The input is modified without proportional extra storage.

A simple way to remember these patterns is:

Fixed additional memory = O(1)
Logarithmic additional memory = O(log n)
Linear additional memory = O(n)
Two-dimensional n × n storage = O(n²)

Frequently Asked Questions

1. What is space complexity?

Space complexity describes how the memory requirements of an algorithm grow as the input size increases. It focuses on the growth of memory rather than the exact amount of memory used on a particular machine.

2. What is the difference between space complexity and auxiliary space?

Space complexity can describe the overall memory requirement, including input and additional memory depending on the context. Auxiliary space specifically refers to the extra memory used by the algorithm apart from the input.

3. Does a loop always increase space complexity?

No. A loop may execute n times while using O(1) auxiliary space if it repeatedly reuses the same variables. Space increases when the algorithm stores additional data that grows with the input.

4. How does recursion affect space complexity?

Each active recursive function call requires memory on the call stack. The maximum recursion depth determines the stack-space contribution, such as O(n) for linear recursion or O(log n) for logarithmic recursion.

5. Can an algorithm have O(n) time and O(1) space?

Yes. An algorithm can process n elements one at a time while using only a fixed number of additional variables. In that case, its time complexity can be O(n) while its auxiliary space remains O(1).