Core Concept Mastery • DSA Module
Space complexity is how much extra memory the search uses. Iterative binary search (with a loop) only needs a few variables (low, high, mid), so O(1). Recursive binary search (function calls itself) uses the call stack, so O(log n) because there are about log n calls.
How much extra memory does the search need?
Uses a loop. Only stores variables low, high, mid.
Uses function calls. Creates a stack frame for each split.
Space: O(log n)O(1)
Only a few variables: low, high, mid. Same for any size array.
O(log n)
Each recursive call uses stack memory. About log n calls.
Iterative (loop)
We use a loop. We only need three variables: low, high, and mid. No matter how big the array is, we do not need more variables. So space is O(1).
Recursive (function calls itself)
Each time we call the function, the computer saves where we are (on the call stack). We call the function about log n times (once per "cut in half"). So we have about log n stack frames. So space is O(log n).
For binary search, the iterative version uses less memory. The recursive version is easier to read but uses stack space. For very large arrays, O(1) space can matter.