Space complexity

Auxiliary space is the extra memory an algorithm allocates beyond its input: temporary arrays, hash maps, recursion frames. Reversing an array with two indexes uses O(1) auxiliary space; copying it into a new array uses O(n). Space complexity is usually reported as auxiliary space.

Count every allocation that grows with n, including those inside helper calls.

1static void reverse(int[] a) {                // O(1) auxiliary
2    for (int i = 0, j = a.length - 1; i < j; i++, j--) { int t = a[i]; a[i] = a[j]; a[j] = t; }
3}
4static int[] reversed(int[] a) {               // O(n) auxiliary
5    int[] r = new int[a.length];
6    for (int i = 0; i < a.length; i++) r[i] = a[a.length - 1 - i];
7    return r;
8}

Input space is the memory occupied by the input itself, such as the array passed in. Total space = input space + auxiliary space. Algorithms are compared on auxiliary space because the input is fixed by the problem.

State your convention. Saying “O(n) space” without it is ambiguous when the input itself is of size n.

Each active call stores a frame (arguments, locals, return address). A recursion of depth d uses O(d) stack space, even if it allocates nothing else. Factorial uses O(n); binary search written recursively uses O(log n); merge sort uses O(log n) stack plus the O(n) merge buffer.

The JVM's default stack allows roughly 10,000 to 20,000 frames. Deeper recursion throws StackOverflowError; convert to a loop or raise -Xss.

1static long factorial(int n) {
2    if (n == 0) return 1;              // base case
3    return n * factorial(n - 1);       // recursive case
4}

An in-place algorithm transforms its input using O(1) extra space (some definitions allow O(log n) for the recursion). Heap sort, insertion sort, the two-pointer partition in quick sort and the reverse above are in place. Merge sort on arrays is not.

In place saves memory but loses the original data and can complicate the code.

You can often buy speed with memory. A hash set makes membership O(1) at O(n) space; memoisation turns exponential Fibonacci into linear time using an O(n) table; precomputed prefix sums make range queries O(1) with an extra array. The reverse trade, less memory for more time, is typical for streaming and low-memory devices.

Choose by constraints: a tight memory limit may force a slower approach.

Peak memory is the largest amount in use at any moment, which is what a memory limit actually checks. An algorithm that allocates and frees many temporary arrays can have a small peak even if its total allocation is large. Conversely, holding two copies of a big structure at once doubles the peak.

Measure with a profiler or Runtime.getRuntime().totalMemory() - freeMemory() before and after a step, and run System.gc() first only for experiments.

1Runtime rt = Runtime.getRuntime();
2long before = rt.totalMemory() - rt.freeMemory();
3int[] big = new int[10_000_000];                 // about 40 MB
4long after = rt.totalMemory() - rt.freeMemory();
5System.out.println((after - before) / 1_000_000 + " MB");

Java has a garbage collector, but it only frees objects that are unreachable. A leak is an object you no longer need that remains reachable: a growing static List, an unbounded cache, listeners that were never removed, or an array-based stack that does not null out popped slots.

Fix by removing references when done, bounding caches (for example with an LRU policy), and using weak references where appropriate.

1class ArrayStack<T> {
2    private Object[] data = new Object[16]; private int size;
3    void push(T v) { if (size == data.length) data = Arrays.copyOf(data, size * 2); data[size++] = v; }
4    @SuppressWarnings("unchecked")
5    T pop() {
6        T v = (T) data[--size];
7        data[size] = null;        // without this line the popped object stays reachable: a leak
8        return v;
9    }
10}