Space complexity

Space complexity measures how much extra memory an algorithm needs as its input grows, the way Big-O measures time. It counts the structures you allocate, like a hash map holding every element, and also the hidden cost of the call stack: every recursive call that hasn’t returned yet keeps a frame alive. That’s why a recursive walk down a long chain uses memory proportional to its length even though you never allocated anything by hand, and why very deep recursion can crash with a stack overflow. It’s the other half of most trade-offs, since you often buy speed by spending memory on a cache or lookup table.