Space Complexity

Concept

While Time Complexity measures execution speed, Space Complexity measures how much additional memory (RAM) your algorithm requires to complete its task as the input data ($N$) grows.

It is crucial to understand that Space Complexity only refers to the Auxiliary Space (the extra space the algorithm uses internally), not the space required to hold the initial input data itself.

Mental Model

Imagine you have a deck of 52 playing cards, and you need to sort them.

• $O(1)$ Space (In-Place): You sort the cards physically in your hands, swapping cards one by one. You didn’t need any extra tables or boxes to do the work. The space used is constant, regardless of if you have 52 cards or 1,000,000 cards.
• $O(N)$ Space: You buy a brand new box. You look through your hand, find the smallest card, put it in the new box, and repeat. You needed a second box exactly large enough to hold all $N$ cards.

Calculating Space Complexity

You calculate space exactly the same way you calculate time: look at the variables, arrays, and hash maps you create inside the function.

// 1. O(1) Space: Constant Space
function getSum(arr: number[]): number {
    let sum = 0; // Uses 1 integer of memory
    for (let num of arr) {
        sum += num;
    }
    return sum; // No matter how big 'arr' is, we only use 1 extra variable.
}

// 2. O(N) Space: Linear Space
function getEvens(arr: number[]): number[] {
    const evens = []; // Creates a new array!
    for (let num of arr) {
        if (num % 2 === 0) evens.push(num);
    }
    return evens; // In the worst case, we duplicate the entire array.
}

// 3. O(N^2) Space: Quadratic Space
function createMatrix(n: number): number[][] {
    const matrix = []; 
    for (let i = 0; i < n; i++) {
        matrix.push(new Array(n).fill(0)); // Creates an N x N grid
    }
    return matrix;
}

The Hidden Trap: The Call Stack (Recursion)

The most common trap in Space Complexity is Recursion.
Variables explicitly declared in code aren’t the only things that consume memory. The CPU Call Stack consumes memory.
If a recursive function calls itself $N$ times before hitting the base case, the CPU must keep $N$ frames of execution open in memory simultaneously.

Therefore, a recursive function that creates zero new variables but recurses $N$ levels deep has a Space Complexity of $O(N)$.

function recursiveCountdown(n: number): void {
    if (n === 0) return;
    // O(N) Space because the Call Stack gets N frames deep!
    recursiveCountdown(n - 1);
}

The Time/Space Trade-off

In Software Engineering, you can almost always make an algorithm run faster (better Time Complexity) by throwing more RAM at it (worse Space Complexity).
For example, instead of running an $O(N)$ loop to search for a value in an array every time, you can pre-calculate the array into a Hash Map (taking $O(N)$ extra space). Now, your time to search drops to $O(1)$ instant lookup.

Interview Questions

Q: You are asked to reverse an array. You can either use .map() to build a new reversed array, or you can use a Two-Pointer approach to swap the existing elements. Which is better?
A: The Two-Pointer approach is vastly superior.
Building a new array requires $O(N)$ Space Complexity. If the array is 10 Gigabytes, you just consumed 10 Gigabytes of extra RAM.
The Two-Pointer approach modifies the existing array “In-Place”. It uses two variables (left index and right index) and a temporary swapping variable. Therefore, it requires $O(1)$ Space Complexity, consuming almost zero extra RAM, while maintaining the exact same $O(N)$ Time Complexity.

Q: What is the space complexity of Depth First Search (DFS) vs Breadth First Search (BFS) on a Binary Tree?
A: DFS: Uses recursion, so the space complexity is dictated by the maximum height of the tree (the Call Stack). In the worst case (a completely unbalanced, straight-line tree), the space is $O(N)$. In a perfectly balanced tree, the height is only $O(\log N)$.
BFS: Uses a Queue data structure to hold the nodes of the current level. The widest level of a Binary Tree is the very bottom level, which holds roughly $N/2$ nodes. Therefore, the Space Complexity of a Queue-based BFS is always $O(N)$ in the worst case.