Space Complexity
Visualize how memory usage grows with recursive calls (Stack Space).
Input Size (N): 5
Ready to visualize recursion stack.
Stack is empty
Memory Usage
Intuition
Just like time complexity measures operations, space complexity measures the extra memory an algorithm needs as the input grows.
Concept
- Auxiliary Space: Extra space used (e.g., temp arrays, recursion stack).
- Input Space: Space to store the input itself (usually ignored in analysis).
- O(1) Space: Uses fixed memory regardless of N (e.g., iterative loops).
- O(N) Space: Memory grows linearly (e.g., recursion depth of N).
How it Works
Recursion Stack:
Every time a function calls itself, the computer must "remember" where to return to. This info is stored in a "Stack Frame". If you call a function N times recursively, you use O(N) stack space.
Step-by-Step Breakdown
Watch the visualization:
- Each
factorial(n)call adds a block to the stack. - The stack grows until the base case is reached.
- Then, frames are popped off as functions return.
When to Use
- When optimizing for devices with limited RAM (embedded systems, mobile).
- To avoid "Stack Overflow" errors in deep recursion.
When NOT to Use
- When you have plenty of memory and recursion makes code cleaner.
How to Identify
"Memory Limit Exceeded", "In-place algorithm required", "O(1) extra space".
Sample Problems
Frequently Asked Questions
What is Space Complexity?
Visualize how memory usage grows with recursive calls (Stack Space).
What is the time complexity of Space Complexity?
The time complexity is: Best case N/A, Average case N/A, Worst case N/A. Space complexity is varies.