Space complexity and the call stack

Space complexity is the extra memory an algorithm needs as its input grows. The input itself does not count. A few variables are O(1).

A copy of the array, a hash map holding every item, or an output list are O(n). Recursion is the part people forget. Every call that has not finished yet keeps a small record, called a frame, on the call stack.

So recursion that goes n levels deep uses O(n) memory, even if it creates nothing. On large inputs it can crash with a stack overflow, which means the call stack ran out of room. Balanced recursion, like merge sort or a search down a balanced tree, only goes about log n levels deep.