Big-O notation: space complexity

Optimizing Code in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

What is space complexity?

Time complexity described how input size affects runtime
Space complexity describes how input size affect memory usage

Understanding space complexity is crucial for building applications that:

Only use the right amount of memory, and not more
Avoid crashing with errors such as OutOfMemoryError

Big-O Notation

Notation is identical to time complexity.

Some common complexity classes:

O(1): Constant time - size-independent
O(n): Linear time - grows with input size
O(n²): Quadratic time - grows quadratically with input size

A maximum-finder method

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

Whether our array of integers has 10 elements or 10 million, we still only use memory for one single variable, max
The space complexity is O(1) or constant space

A doubling method

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

If our input has n elements, we need space for n additional elements
The space complexity is O(n) because the extra memory needed grows linearly with the input size

A multiplication table method

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

If n is 10, we need 100 cells; if n is 100, we need 10,000 cells
We classifly this as O(n²)

Why is space complexity important?

Memory is a finite resource!

Our previous examples in action, for an input size of 10,000 elements:

findMax, O(1) -> just a few extra bytes
doubleValues, O(n) -> around 40KB of extra memory
multiplicationTable, O(n²) -> around 400MB of extra memory

Bar plot showing 8 byte increase in memory usage for findMax, 40KB for doubleValues, and 400MB for multiplicationTable

Space complexity vs. time complexity

Don't forget:

Sometimes we trade space for time
Sometimes we trade time for space
The right choice depends on your specific constraints

Graphics symbolizing the trade-off between time and space

Let's practice!

Optimizing Code in Java