Space Complexity
Domain: Algorithms
🎯 Motivation
How much extra memory an algorithm needs as input grows. Sometimes you trade memory for speed, or vice versa.
📋 Concrete Example
An in-place sort uses O(1) extra memory — just a few variables. Merge sort uses O(n) extra memory for temporary arrays. A recursive algorithm uses O(depth) stack space.
🔗 Analogy
Packing for a trip. Minimalist packing (O(1) space) means washing clothes often (slower). Bringing many outfits (O(n) space) is faster but needs a bigger suitcase.