Start learning free

LESSON 159 OF 347 · BIG O NOTATION

Space Complexity in C#: Big O for Memory

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:

Constant Space Complexity:

 function sum(a, b) {
    let 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) {
    let numbers = [];
    for (let i = 0; i < n; i++) {
        numbers.push(i);
    }
    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) {
    let numbers = [];
    for (let i = 0; i < n; i++) {
        numbers.push([]);
        for (let j = 0; j < n; j++) {
            numbers[i].push(j);
        }
    }
    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 it's execution (without taking the input values into account).

Space Complexity = Auxiliary Space + Input space

Let's see some examples:

 function sum(arr) {
    let sum = 0;
    for(let num of 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

C# · BIG O NOTATION

Space Complexity in C#, explained

What space complexity measures

Space complexity describes how much memory an algorithm needs as the input grows. It uses the same Big O notation as time complexity, so you drop constants and keep the fastest-growing term. Time asks "how many steps?"; space asks "how many values do I have to hold at once?".

There are two related quantities:

  • Input space: the memory taken by the input itself.
  • Auxiliary (extra) space: the additional memory the algorithm allocates while running, not counting the input.

Total space is the sum of the two. When people say an algorithm "uses O(1) space" in an interview-style problem, they usually mean its auxiliary space.

Constant space: O(1)

static int Sum(int a, int b) {
    int sum = a + b;
    return sum;
}

The method holds a, b and sum: three int values, whatever their sizes. The memory doesn't depend on any input size, so the space is O(1). A loop doesn't change that on its own:

static int SumArray(int[] arr) {
    int sum = 0;
    foreach (int num in arr) {
        sum += num;
    }
    return sum;
}

The input array takes O(n) space, but that is input space. The method adds only two variables, sum and num, so its auxiliary space is O(1).

Linear space: O(n)

static List<int> Generate(int n) {
    List<int> numbers = new List<int>();
    for (int i = 0; i < n; i++) {
        numbers.Add(i);
    }
    return numbers;
}

The list ends up with n numbers, so the memory grows in step with n: O(n). A List<int> keeps its items in an internal array and replaces that array with a larger one when it fills up. The capacity can be larger than the item count, but it stays within a constant factor of it, so the space is still O(n).

Quadratic space: O(n²)

static List<List<int>> GenerateGrid(int n) {
    List<List<int>> numbers = new List<List<int>>();
    for (int i = 0; i < n; i++) {
        numbers.Add(new List<int>());
        for (int j = 0; j < n; j++) {
            numbers[i].Add(j);
        }
    }
    return numbers;
}

There are n rows, and each holds n numbers, so the structure stores n * n values: O(n²). The same count applies to a rectangular array such as new int[n, n] or an array of arrays.

Things specific to C# that affect space

  • Creating an array costs space immediately. new int[n] allocates room for n elements, filled with zeros, even before you store anything. It is O(n) space.
  • Strings are immutable. Every Substring or concatenation allocates a new string. Building a result in a loop with += can create many temporary strings, although the garbage collector reclaims the old ones. A StringBuilder avoids that churn.
  • Slicing copies. A range such as arr[1..4] creates a new array of that length, so it adds space proportional to the slice. A Span<T> is a view and adds O(1).
  • Reference types store references. An array of n strings holds n references, plus the strings themselves, which live elsewhere.
  • Assigning an array doesn't copy it. int[] b = a; makes b point to the same array, so the extra space is O(1). Use Array.Copy or Clone() when you want a real copy.

Recursion uses space too

Each active method call keeps its parameters and local variables on the call stack. A recursive method that goes n calls deep therefore uses O(n) space for the stack, even if it creates no arrays:

static int CountDown(int n) {
    if (n == 0) {
        return 0;
    }
    return CountDown(n - 1);
}

While CountDown(1000) is running, 1,001 calls are waiting on the stack at once. The equivalent loop would use O(1) space, which is one reason iterative solutions are popular when a problem asks for constant space.

How to work out the space of your code

  1. Ignore the input, unless the problem asks for total space.
  2. Count what you allocate: arrays, lists, dictionaries, new strings, and the recursion depth.
  3. Express each in terms of the input size and keep the largest term.
  4. Remember that the output you build may count, depending on the convention. State which one you use.

Key takeaways

  • Space complexity is the memory an algorithm needs relative to its input size, written in Big O.
  • Auxiliary space excludes the input; total space includes it.
  • A fixed number of variables is O(1), one collection that grows with n is O(n), and an n by n structure is O(n²).
  • Copies, new strings and recursion depth all cost memory in C#, even when no variable is declared for them.
Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free