space complexity

Space complexity is the memory twin of time complexity: as the input grows, how much extra memory does the algorithm need? Just as we count steps for time, here we count storage — how many cells, how big a stack of pending calls, how large the helper arrays — as a function of the input size n, and describe its growth with Big-O. Time tells you whether you will finish; space tells you whether you will fit. A program that is fast but demands more memory than the machine has will simply crash, so both costs matter.

We usually mean auxiliary space: the extra memory an algorithm uses beyond the input it was handed. Summing a list of numbers needs just one running total no matter how long the list is, so it is O(1) extra space. Merge sort builds temporary arrays as it merges, needing O(n) extra space. A recursive algorithm quietly uses memory too: each pending call sits on the call stack, so a recursion that goes n levels deep costs O(n) stack space, and one that goes log n deep costs O(log n) — a real cost beginners often forget.

Recognizing space complexity reveals one of the most common trades in all of programming: time versus space. You can often make something faster by remembering more (a hash table or a memoization cache turns repeated O(n) scans into O(1) lookups, at the price of memory), or shrink memory by recomputing things (saving space but spending time). Knowing both complexities lets you place your algorithm honestly on that trade-off instead of being surprised by it later.