Analyzing Space Complexity

What is Space Complexity?

Just as time complexity measures how an algorithm's runtime scales with its input size, space complexity measures how the amount of memory it requires scales with the input size. We use the same Big O notation to express this relationship.

However, a critical distinction must be made. When we analyze space, we often care most about the additional memory the algorithm needs, beyond what's used to store the input data. This leads to two key concepts:

1. Input Space: The memory required to store the input to the algorithm. For a function that takes an array of size n, the input space is typically O(n).
2. Auxiliary Space: The extra or temporary memory that an algorithm uses during its execution. This includes variables created within the function, data structures used for processing, and, as we'll see, the memory used by the call stack during recursion.

The total space complexity is the sum of these two components.

Space Complexity = Input Space + Auxiliary Space

In many contexts, especially in technical interviews, when someone asks for the "space complexity," they are implicitly asking for the auxiliary space complexity. It's always a good practice to clarify which one is being requested. For our purposes, we will analyze both and be explicit about the distinction.

Let's begin by reading a concise article that defines these terms and provides simple examples.

Analyzing Space in Iterative Algorithms

With the core definitions in place, let's analyze the space complexity of some common patterns in iterative code. The principles are very similar to what you've already learned for time complexity.

O(1) — Constant Space

An algorithm has constant auxiliary space complexity if the amount of memory it uses does not change with the input size.

Consider this function to sum the elements of an array:

public int sumArray(int[] array) {
    int sum = 0; // O(1) auxiliary space
    for (int num : array) {
        sum += num;
    }
    return sum;
}

• Input Space: The input is an array of size n. So, the input space is O(n).
• Auxiliary Space: The algorithm only creates a few variables (sum and num). The amount of memory for these variables is fixed, regardless of whether the array has 10 elements or 10 million. Therefore, the auxiliary space is O(1).
• Total Space Complexity: O(n) + O(1) = O(n).

This is a very common pattern: an algorithm that processes a large input but only uses a small, fixed number of extra variables.

O(n) — Linear Space

An algorithm has linear auxiliary space complexity if the extra memory it uses grows proportionally with the input size. This typically happens when you create a new data structure whose size depends on the input.

public int[] copyArray(int[] array) {
    int n = array.length;
    int[] newArray = new int[n]; // O(n) auxiliary space
    for (int i = 0; i < n; i++) {
        newArray[i] = array[i];
    }
    return newArray;
}

• Input Space: The input array takes O(n) space.
• Auxiliary Space: The algorithm creates a newArray of the same size as the input. The memory required for this new array scales linearly with n. Thus, the auxiliary space is O(n).
• Total Space Complexity: O(n) + O(n) = O(n).

The Baeldung article you'll read next provides a clear walkthrough of calculating space for these exact kinds of examples.

The Special Case: Space Complexity of Recursion

Analyzing the space complexity of recursive algorithms requires us to consider the call stack. Every time a function is called, a block of memory called an activation record (or stack frame) is pushed onto the call stack. This record stores the function's parameters, local variables, and the return address. When the function returns, its stack frame is popped off the stack.

For a recursive algorithm, the space complexity is determined not by the total number of recursive calls, but by the maximum number of stack frames on the call stack at any single point in time. This is equivalent to the greatest depth of the recursion.

Let's look at a simple recursive factorial function:

public int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

When you call factorial(4), the call stack will look like this at its deepest point:

1. factorial(1)
2. factorial(2)
3. factorial(3)
4. factorial(4)
5. main()

The depth of recursion is 4. For an input n, the depth will be n. Each call adds a constant amount of space to the stack for its parameters and local variables. Therefore, the auxiliary space complexity of this recursive factorial is O(n).

This is a critical point: the iterative version of factorial has O(1) auxiliary space, while the recursive version has O(n) auxiliary space due to the call stack.

The following image of a recursion tree for the Fibonacci sequence provides an excellent visual for this concept.

To solidify your understanding of how the call stack depth determines space complexity, we'll consult a short video that explains this concept with clear animations.

The Space-Time Tradeoff

In software engineering, you'll often face a classic dilemma: do you optimize for speed or for memory? This is known as the space-time tradeoff. It's rarely possible to have the best of both. Often, making an algorithm faster requires using more memory, and vice-versa.

A perfect example of this is memoization, a technique you might use to optimize a recursive function. Consider the naive recursive Fibonacci algorithm. Its time complexity is exponential, O(2^n), because it recomputes the same values over and over.

We can trade space for time by storing the results of previous computations in a data structure like a HashMap.

// O(2^n) time, O(n) space (due to recursion depth)
public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// O(n) time, O(n) space (for cache + recursion depth)
private Map<Integer, Integer> cache = new HashMap<>();
public int fibWithMemoization(int n) {
    if (n <= 1) return n;
    if (cache.containsKey(n)) {
        return cache.get(n);
    }
    int result = fibWithMemoization(n - 1) + fibWithMemoization(n - 2);
    cache.put(n, result);
    return result;
}

By using O(n) auxiliary space for the cache, we dramatically reduce the time complexity from O(2^n) to O(n). This is a classic space-time tradeoff and a fundamental concept in algorithm design and dynamic programming.

The Baeldung article has an excellent section that discusses this tradeoff using this exact example.

Conclusion

In this lesson, we rounded out your foundational knowledge of complexity analysis by focusing on memory usage. You now understand the critical difference between an algorithm's overall space complexity and its auxiliary space usage, which is often the more important metric for optimization.

Key Takeaways:

• Space Complexity measures an algorithm's memory usage as a function of its input size.
• Total Space = Input Space + Auxiliary Space. Auxiliary space is the extra memory used during execution.
• Analyzing iterative algorithms involves identifying variables and data structures whose size depends on the input n.
• For recursive algorithms, the auxiliary space complexity is determined by the maximum depth of the call stack, not the total number of calls.
• The space-time tradeoff is a fundamental principle where you can often reduce an algorithm's runtime at the cost of increasing its memory usage.

We have now covered the "what" and "how" of analyzing both time and space. In our next lesson, we will add a final layer of precision by exploring best-case, worst-case, and average-case analysis, which will allow you to describe an algorithm's performance under different conditions.