🧮Space Complexity
Also known as Memory Complexity
How much extra memory a task needs. It grows with the input.
Think of it like
Think of it like a recipe. A bigger cake needs more bowls.
Example
Jack's first version copied a 2 GB file into memory to count its lines. Reading it one line at a time cut the memory to a few kilobytes.
Why it matters
Memory runs out before time does on phones, small servers and huge data sets.
Definition
Common mistake
Key takeaways
- 1Extra memory. Beyond the input itself.
- 2Written in Big O. O(1), O(n) and so on.
- 3Trade with time. More memory, fewer steps.