Space complexity

Fundamentals

At a glance

Space complexity concerns memory usage as input grows. Distinguish total space, including storage for the input, from auxiliary space, the extra memory used by the algorithm beyond the input itself.

For example, sorting an existing array in place may need only O(1) extra memory even though the input array occupies O(n) space.

Where memory goes

• Input storage: an array with n integers uses space proportional to n.
• Temporary arrays and buffers: copying n values into another array adds O(n) auxiliary space.
• Call stack: recursion consumes stack frames, even when there is no explicit additional array.
• Fixed locals: a small constant number of counters or references is O(1) auxiliary space.

Compare two implementations

C#

C# | InPlace.cs

static void DoubleInPlace(int[] values)
{
    for (int i = 0; i < values.Length; i++)
        values[i] *= 2;
}

C++

C++ | InPlace.cpp

#include <vector>
void doubleInPlace(std::vector<int>& values) {
    for (int& value : values) value *= 2;
}

This changes the existing array and uses a constant number of extra variables. Its auxiliary space is O(1).

C#

C# | Copy.cs

static int[] DoubledCopy(int[] values)
{
    int[] output = new int[values.Length];
    for (int i = 0; i < values.Length; i++)
        output[i] = values[i] * 2;
    return output;
}

C++

C++ | Copy.cpp

#include <vector>
std::vector<int> doubledCopy(const std::vector<int>& values) {
    std::vector<int> result;
    result.reserve(values.size());
    for (int value : values) result.push_back(value * 2);
    return result;
}

This produces a new array, so it requires O(n) auxiliary space.

Recursive algorithms

A recursive binary search may use O(log n) call-stack space even when its iterative equivalent uses O(1) extra space. The depth of recursion is as important as the size of explicit temporary collections.

Analyze time and space separately

Both implementations above visit all items, so both take O(n) time. Their auxiliary space costs are different.

Ownership and lifetime matter

A temporary array contributes to auxiliary space even if it is returned later or freed after the method completes. The input collection itself is often excluded from auxiliary-space analysis, so always state the convention being used. A function returning a new result with n values generally needs space proportional to n for that result.

Recursion versus iteration

Recursion may look short in source code, but each active call needs a stack frame. A linear recursion can use O(n) additional call-stack space even when it allocates no arrays. An equivalent iterative implementation can sometimes use O(1) extra space.

Real memory usage

Objects have headers, arrays may reserve capacity and managed runtimes introduce garbage-collection behavior. A constant number of temporary objects is still constant-space in the asymptotic model, although excessive allocations can hurt frame time. In practice, combine complexity analysis with allocation profiling.

Further reading

↗External referenceGeeksforGeeks: Space ComplexityExplore how much additional memory an algorithm uses.

• Merge sort, which uses a reusable merge buffer

Other space-growth families

Two useful classifications from the Obsidian notes describe families of space bounds rather than a single fixed growth rate.

Polylogarithmic space: O((log n)^c)

For a fixed positive constant c, an algorithm using O((log n)^c) auxiliary cells has polylogarithmic space. For example, a table with approximately log₂(n) rows and log₂(n) columns occupies O((log n)²) cells. O(log n) is the particular case c = 1. For any fixed ε > 0, (log n)^c grows asymptotically more slowly than n^ε. Remember that c is fixed as n changes; it is not another input variable that grows with the problem.

int side = (int)Math.Log2(n) + 1; // n >= 1
int[,] workspace = new int[side, side]; // O((log n)^2) cells

Polynomial space: O(n^c)

For a fixed constant c >= 0, polynomial space is the family O(n^c). It includes constant (c = 0), linear (c = 1), quadratic (c = 2) and cubic (c = 3) bounds. A two-dimensional n × n matrix is quadratic, while an n × n × n array is cubic. The exponent is a fixed constant; if it grows with the input, the expression is no longer a polynomial-space bound under this definition.

These are descriptions of memory growth, not promises about how many CPU operations the algorithms perform. See the complexity learning map for examples of the individual classes.