Space Complexity and the Call Stack

1.What counts as extra space

Space complexity counts memory the algorithm creates beyond the input: new arrays, maps, sets, strings and the call stack. A few variables are O(1). A hash set of up to n elements is O(n). A 2D table of n × m is O(n·m).

The output usually isn't counted (returning a list of n items doesn't make an O(1) algorithm O(n)), but say so explicitly in interviews.

2.Recursion uses stack memory

Every recursive call waits on the call stack until its child calls return. A recursion that goes n levels deep uses O(n) space even if each call only has a few variables, and very deep recursion (around 10,000+ levels with default settings) can crash with StackOverflowError.

public class Main {
    static int depth(int n) {
        if (n == 0) return 0;
        return 1 + depth(n - 1);     // n frames are on the stack at the deepest point
    }
    public static void main(String[] args) {
        System.out.println(depth(5_000));
    }
}

5000

3.Trading space for time

Many speed-ups store something to avoid recomputing it: a hash set of seen values (O(n) space) turns an O(n²) pair search into O(n). Whether that trade is good depends on the limits, but in interviews time is usually the priority as long as memory stays reasonable.