DSA Patterns (Multi-Lang)•Part 1: Intro, Approach & Complexity Analysis (1 - 5)
Space Complexity: Call Stack vs Heap.
In Simple Words:
- Call Stack: Used for function recursion. Each recursive call adds a stack frame. Deep recursion of depth $N$ consumes $O(N)$ stack memory, risking
StackOverflowErrorif $N > 10^4$. - Heap Memory: Used for dynamic data structures (
new Map(),new Array(), iterative queues). Bounded only by total system RAM.
Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++
Switch tabs or choose All# Recursive: O(N) Call Stack memory (danger of RecursionError for deep N)
def sum_recursive(n: int) -> int:
if n <= 1:
return n
return n + sum_recursive(n - 1)
# Iterative: O(1) Auxiliary space (safe for any N)
def sum_iterative(n: int) -> int:
total = 0
for i in range(1, n + 1):
total += i
return total