A lesson from the Computer Memory module of the bootcamp. About a 12 minute read.
Space complexity is how the memory an algorithm needs grows with its input, and it is the half of Big-O that people answer carelessly. This lesson counts it the way the machine does: the extra space you allocate, the stack your recursion quietly uses, the copies your language makes behind your back, and what each element really costs in bytes.
SPACE COMPLEXITY is the growth rate of the memory an algorithm needs, written in the same Big-O as time. The convention in interviews and most textbooks is AUXILIARY space: what you allocate beyond the input itself, so sorting an array in place is O(1) space even though the array is n. The output usually does not count either, since you cannot return n answers in less than n space. When there is any doubt, say which you mean. 'O(n) total, O(1) extra' is a complete answer. 'O(1)' on its own, for a function that builds and returns a new list, is the kind of answer that gets a follow-up question.
The rest of this lesson continues with 6 further sections. See the full curriculum.
Browse all 546 practice puzzles