What is the space complexity of a method that counts the vowels in a String?

O(1) auxiliary space. The method needs only a counter and a loop index, whatever the length of the string. The string itself is input space, which the caller already paid for.

What is the space complexity of BFS on a grid of m rows and n columns?

O(m × n). The visited array has one cell per grid position, and in the worst case the queue can also hold a large fraction of the cells at once. Both are bounded by m × n.

Why is recursive binary search O(log n) space while the iterative version is O(1)?

Each recursive call halves the range and stays on the stack until the search ends, so at most about log2 n frames exist at once. The loop version keeps three variables in a single frame.

Why does an ArrayList not release memory after you remove most of its elements?

Removing elements lowers the list's size, but the backing array keeps its capacity, so its memory stays allocated. Call trimToSize() to shrink the array to the current size, or create a new list if you no longer need the old one.

Does a tail-recursive method in Java use less stack space than ordinary recursion?

No. The Java compiler and the HotSpot JVM do not perform tail-call optimisation, so every call still gets its own frame and the method uses O(n) stack space for n calls. To get O(1) space, rewrite the method as a loop.

What is the auxiliary space of merge sort on an array compared with on a linked list?

On an array, merge sort needs an O(n) helper array to merge into. On a linked list, merging only changes next references, so no helper array is needed; the remaining cost is the recursion stack, O(log n) for the top-down version.

A job reads a 10 GB log file and stores every line in a List before processing it. How would you reduce its space complexity?

Process the file as a stream instead of loading it all. For example, read it line by line with BufferedReader.readLine() or Files.lines() and update running totals for each line. Memory then depends on the longest line and the size of the results, not on the file size, which turns O(n) space into close to O(1).

Space Complexity in Data Structures

Space complexity in data structures describes how much memory an algorithm needs as its input size n grows. Like time complexity, it is written in Big-O notation: O(1) means the extra memory stays the same no matter how large the input is, while O(n) means it grows in step with the input.

Memory matters more than many developers expect. A server handling thousands of requests at once multiplies every per-request allocation, a mobile device has little memory to spare, and in Java every extra object also creates work for the garbage collector.

Input Space and Auxiliary Space

The memory used while an algorithm runs has two parts:

Input space holds the data you were given, such as the array passed to a sorting method.
Auxiliary space is everything extra the algorithm creates: temporary arrays, collections, local variables and the stack frames of recursive calls.

Total space is the sum of the two. When people compare algorithms, they almost always mean auxiliary space, because every algorithm that receives the same input pays the same input space. Saying that a method which only reads an array "uses O(n) space" is technically true but unhelpful; its auxiliary space is O(1), and that is the number that tells the two algorithms apart.

Where Java Keeps Your Data: Stack and Heap

To reason about space in Java, it helps to know where things are stored:

The stack belongs to one thread. Each method call pushes a frame holding that call's local variables: primitive values such as int and double, and references to objects. The frame disappears when the method returns.
The heap is shared by the whole program. Every object and every array lives there, even when only a local variable refers to it. Heap memory is reclaimed by the garbage collector once nothing refers to the object any more.

This explains two common surprises. First, a recursive method can run out of memory without creating a single object, because its frames pile up on a stack of limited size. Second, a local variable such as int[] copy = new int[n] costs O(n), not O(1): the variable is only a reference on the stack, but the array it points to occupies n slots on the heap.

Common Space Complexities

Auxiliary space	What it looks like	Example
O(1)	A fixed number of variables, whatever the input size	Reversing an array in place, finding the maximum
O(log n)	Recursion that halves the problem at each level	Recursive binary search; average stack depth of quick sort
O(n)	One extra structure the size of the input, or recursion n levels deep	Copying an array, a `HashSet` of seen values, merge sort
O(n²)	A two-dimensional table over the input	An adjacency matrix for n vertices

An algorithm that needs only O(1) auxiliary space is called in-place. Bubble, selection and insertion sort are in-place; merge sort is not, because it merges into a helper array.

Recursion and the Call Stack

Recursion is the most commonly forgotten source of space usage. The program below sums an array recursively and iteratively, and reverses it by copying and in place. It records the deepest the call stack goes and how many extra array cells each approach allocates.

ExtraSpaceTracker.java

public class ExtraSpaceTracker {

    static int depth;       // current number of active calls
    static int maxDepth;    // deepest the call stack has been

    // Recursive sum: every element adds one stack frame -> O(n) extra space
    static long recursiveSum(int[] values, int index) {
        depth++;
        maxDepth = Math.max(maxDepth, depth);
        long result = (index == values.length) ? 0
                : values[index] + recursiveSum(values, index + 1);
        depth--;
        return result;
    }

    // Iterative sum: one frame and a couple of local variables -> O(1) extra space
    static long iterativeSum(int[] values) {
        depth++;
        maxDepth = Math.max(maxDepth, depth);
        long total = 0;
        for (int value : values) {
            total += value;
        }
        depth--;
        return total;
    }

    // Reverse into a new array -> O(n) extra space
    static int[] reversedCopy(int[] values) {
        int[] copy = new int[values.length];
        for (int i = 0; i < values.length; i++) {
            copy[i] = values[values.length - 1 - i];
        }
        return copy;
    }

    // Reverse in place with one temporary variable -> O(1) extra space
    static void reverseInPlace(int[] values) {
        for (int left = 0, right = values.length - 1; left < right; left++, right--) {
            int temp = values[left];
            values[left] = values[right];
            values[right] = temp;
        }
    }

    public static void main(String[] args) {
        System.out.printf("%7s %16s %16s %18s %16s%n",
                "n", "recursive frames", "iterative frames", "copy: extra cells", "in place: extra");
        for (int n : new int[] {10, 1_000, 5_000}) {
            int[] values = new int[n];
            for (int i = 0; i < n; i++) {
                values[i] = i + 1;
            }

            maxDepth = 0;
            recursiveSum(values, 0);
            int recursiveFrames = maxDepth;

            maxDepth = 0;
            iterativeSum(values);
            int iterativeFrames = maxDepth;

            int copyCells = reversedCopy(values).length;
            reverseInPlace(values);                  // allocates no array

            System.out.printf("%,7d %,16d %,16d %,18d %16s%n",
                    n, recursiveFrames, iterativeFrames, copyCells, "1 temp variable");
        }
    }
}

Output

      n recursive frames iterative frames  copy: extra cells  in place: extra
     10               11                1                 10  1 temp variable
  1,000            1,001                1              1,000  1 temp variable
  5,000            5,001                1              5,000  1 temp variable

The recursive sum needs n + 1 frames: one for each element plus the final call that reaches the end of the array. Its auxiliary space is therefore O(n), even though it never creates an object. The iterative version uses a single frame however large the array is: O(1). The same contrast appears with reversal: copying costs n extra cells, while swapping in place needs just one temporary variable.

What happens internally: the stack has a fixed size, set with the JVM option -Xss (typically 1 MB on 64-bit Linux and Windows, 2 MB on Apple Silicon Macs). When too many frames pile up, the JVM throws StackOverflowError. A simple recursive method like the one above failed after roughly 15,000 to 25,000 calls in our JDK 21 test, long before the heap is full. Java does not optimise tail calls, so rewriting a method in tail-recursive form does not save stack space; converting it to a loop does.

Big-O Versus Real Bytes in Java

Two structures with the same space complexity can use very different amounts of memory. Both an int[] and an ArrayList<Integer> need O(n) space, but on a typical 64-bit HotSpot JVM with compressed references (the default for heaps smaller than 32 GB):

an int stored in an int[] takes 4 bytes;
an Integer object takes 16 bytes (a 12-byte object header plus the 4-byte value), and the list stores a 4-byte reference to it.

A quick measurement on JDK 21 with five million values confirmed about 4 bytes per element for the array and about 20 for the list: five times more memory for the same O(n). Values from −128 to 127 are an exception, because Integer.valueOf returns shared cached objects for them.

Other hidden costs follow the same pattern. Since Java 7, substring copies the characters into a new string instead of sharing the original. An ArrayList keeps its larger backing array after you remove elements, until you call trimToSize(). And since Java 9, a String containing only Latin-1 characters stores one byte per character instead of two.

The Space-Time Trade-off

Memory and speed can often be exchanged. A HashSet of values already seen turns an O(n²) duplicate check into an O(n) one, at the cost of O(n) extra memory. Memoization stores earlier results so they never have to be recomputed. In the other direction, sorting an array in place and comparing neighbours finds duplicates in O(n log n) time with little extra memory. The right choice depends on which resource is scarcer in your situation.

Conclusion

Space complexity in data structures measures how an algorithm's memory needs grow with its input. Focus on auxiliary space, remember that every recursive call takes a stack frame, and keep in mind that Big-O hides real costs such as boxing. With these habits you can spot memory-hungry code before it causes a StackOverflowError or an OutOfMemoryError in production.

Help Us Improve