Big O notation · part 5 of 8
What space complexity is
Everything so far has been about time, but that's only one side of the coin. The other is memory.
Space, the other axis
Luckily for us, memory works in exactly the same way as time: space complexity is how much extra memory grows with n.
Look back at our duplicate finders. The every-pair version held nothing extra, just a couple of loop counters, so it's O(1) space. The Set version can grow to hold every card, so it's O(n) space. We spent O(n) memory to drop from O(n²) time down to O(n). That trade, memory for speed, is one of the most common moves you'll make, and big O is how you describe both sides of it.
Recursion naturally costs space too. Every call that hasn't returned yet is sitting on the call stack, so a recursion that goes n deep is using O(n) space even if it hands back a single number at the end.
You will likely be asked for both time and space. "O(n) time, O(1) space" is a complete answer. Even if you're not asked for both, giving only the time is giving half of it. A good interviewer will just ask for the other half, but you'll probably get some bonus points volunteering it.