Logarithmic Space Complexity (Recursion depth)

Recursive algorithms that halve the problem size use $O(\log n)$ space for the call stack. For example, binary search's recursive version has recursion depth $O(\log n)$.

Each recursive call adds a stack frame. With $\log_2(n)$ levels of recursion, you use $O(\log n)$ stack frames, each holding a constant amount of data.

You can often convert recursive solutions to iterative ones to reduce space from $O(\log n)$ to $O(1)$, but the time complexity stays the same.