Start learning free

LESSON 218 OF 414 · BIG O NOTATION

Space Complexity in Rust: O(1), O(n), O(n²) and Auxiliary Space

Reading Read the full explanation

Space Complexity measures the total amount of memory that an algorithm or operation needs to run according to its input size.

Space Complexity is a parallel concept to Time Complexity. We express space complexity measurements using the Big-O notation, following the same guidelines like we do for time complexity.

Now let's learn how to compute space complexity by taking a few examples (written in pseudo-code, so they apply to any language):

Constant Space Complexity:

function add(a, b):
    sum = a + b
    return sum

In the example above, we use 3 number variables: a and b, which are input variables and sum, which is an auxiliary variable.

And because the space requirement is fixed (3 number variables), hence it is called Constant Space Complexity and is noted with O(1).

Linear Space Complexity:

function generate(n):
    numbers = empty list
    for i from 0 to n - 1:
        add i to the end of numbers
    return numbers

In the example above, we use an auxiliary array numbers which is populated with n numbers.

Since the total space requirement is n numbers, the Space Complexity is increasing linearly with the increase in the input value n, hence it is called as Linear Space Complexity and is noted with O(n).

Quadratic Space Complexity:

function generate(n):
    numbers = empty list
    for i from 0 to n - 1:
        add an empty list to the end of numbers
        for j from 0 to n - 1:
            add j to the end of the row at index i
    return numbers

In the example above, we use an auxiliary 2D array numbers of n rows and n columns.

Since the total space requirement is n^2 numbers, the Space Complexity is directly proportional to the squared of the input value n, hence it is called as Quadratic Space Complexity and is noted with O(n^2).

Extra/Auxiliary Space:

Sometimes Extra/Auxiliary Space is confused with Space Complexity. But Auxiliary Space is the extra space or the temporary space used by the algorithm during its execution (without taking the input values into account).

Space Complexity = Auxiliary Space + Input space

Let's see some examples:

function addAll(arr):
    sum = 0
    for each num in arr:
        sum += num
    return sum

In the example above, we have an input array arr. If we denote its length by n, the Input Space is O(n).

However, we use only 2 auxiliary variables sum and num, so the Extra Space is O(1).

Next lesson

RUST · BIG O NOTATION

Space Complexity in Rust, explained

What space complexity measures

Space complexity is the amount of memory an algorithm needs as a function of its input size, written in the same Big O notation as time complexity and following the same rules: drop constants and lower-order terms, and describe growth, not exact bytes. The question is not "how many bytes?" but "how does the memory grow when the input grows?"

It helps to separate two parts. The input space is the memory the input itself occupies. The auxiliary space is the extra memory the algorithm allocates while it works, not counting the input. The total is input space plus auxiliary space. In interviews, "space complexity" most often means the auxiliary space, and problem statements say things like O(1) or O(n) extra space.

Constant space: O(1)

fn sum(a: i32, b: i32) -> i32 {
    let sum = a + b;
    sum
}

The function holds three integers: the two parameters and sum. That number does not depend on the values passed in, so the space is constant. Constant space is the goal for algorithms that can work with a few variables, such as a running total or a pair of indices.

Linear space: O(n)

fn generate(n: usize) -> Vec<usize> {
    let mut numbers = Vec::new();
    for i in 0..n {
        numbers.push(i);
    }
    numbers
}

The vector numbers ends up with n elements, so the memory grows in step with n. Calling generate(5) returns [0, 1, 2, 3, 4]. The vector is also the output, but counting it is the safe default unless a problem says otherwise.

Quadratic space: O(n²)

fn generate(n: usize) -> Vec<Vec<usize>> {
    let mut numbers = Vec::new();
    for _ in 0..n {
        let mut row = Vec::new();
        for j in 0..n {
            row.push(j);
        }
        numbers.push(row);
    }
    numbers
}

This builds a grid of n rows with n numbers each. For n = 3 the result is [[0, 1, 2], [0, 1, 2], [0, 1, 2]], nine numbers in total. The space is n × n, so it is O(n²). Tables for dynamic programming and adjacency matrices of graphs are typical examples.

Auxiliary space versus input space

fn sum(arr: &[i32]) -> i32 {
    let mut sum = 0;
    for n in arr {
        sum += n;
    }
    sum
}

If the slice has n elements, the input space is O(n). The function adds two variables, sum and the loop variable n, so its auxiliary space is O(1). With [1, 2, 3] it returns 6. The slice parameter matters here: &[i32] borrows the caller's data, so the call copies nothing. Cloning is what costs space: arr.to_vec() or arr.clone() inside the function would add O(n) auxiliary space.

Recursion uses space too

Memory is not only the collections you create. Every function call that has not returned yet occupies a frame on the call stack. A recursive function that goes n calls deep uses O(n) space, even if it creates no vectors:

fn count_down(n: u32) -> u32 {
    if n == 0 {
        0
    } else {
        1 + count_down(n - 1)
    }
}

count_down(1000) returns 1000 and keeps 1001 frames alive at the deepest point. The same count written as a loop would use O(1) space. The stack has a fixed size, so with a very large n the recursive version can overflow it and abort the program, whereas the loop cannot.

Rust specifics

  • A Vec reserves capacity in advance, so it may hold more memory than its length. That is a constant factor, so Big O ignores it.
  • A HashSet or HashMap holding up to n entries is O(n) space.
  • Passing &v or &mut v shares data without copying, and passing a Vec by value moves it without allocating. Only clone(), to_vec() and collect() into a new collection allocate.
  • Sorting with sort_unstable() works in place, while sort() may allocate a temporary buffer proportional to the length of the slice.

Common mistakes

  • Counting the input as auxiliary space, or forgetting to say which one you are reporting.
  • Forgetting the call stack in recursive solutions.
  • Assuming every clone() is free.
  • Saying O(n) for a loop variable: a single counter is O(1) no matter how many iterations it counts.

Key takeaways

  • Space complexity measures how memory grows with the input: O(1) for a fixed number of variables, O(n) for a collection of n items, O(n²) for an n × n grid.
  • Space complexity is auxiliary space plus input space; the extra memory the algorithm adds is usually what is meant.
  • Recursion depth counts as space.
Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free