Time vs Space Complexity

Every algorithm consumes two resources: time (CPU cycles) and space (memory). Big-O analysis describes both, and most non-trivial design decisions in algorithms are a trade-off between the two.

Time complexity

Counts how many operations the algorithm performs as a function of input size. We count the dominant operations — comparisons in sorting, arithmetic in numerics, recursive calls, hash lookups. Constants and dominated terms are dropped.

Space complexity

Counts the maximum memory an algorithm uses beyond the input itself. It includes auxiliary arrays, recursion call stacks, hash tables, and any allocation that grows with $n$. The input array itself doesn't count toward auxiliary space unless we mutate it in place.

Classic trade-off: memoization

Computing the Fibonacci numbers recursively without memoization takes $O(2^n)$ time and $O(n)$ space (recursion stack). Adding a memoization table makes it $O(n)$ time but uses $O(n)$ extra space for the cache. We pay memory to save time — almost always the right call when memory is plentiful.

When space matters most

Embedded systems, mobile, and very large datasets force you to economize. Algorithms like quicksort are popular partly because they sort in place — $O(\log n)$ stack space versus merge sort's $O(n)$ auxiliary array. On modern hardware, cache behavior often makes the lower-space algorithm faster in practice too.