Big O isn't just about time — it's also about memory (space). Space complexity measures how much extra memory your algorithm uses.
We measure the additional space — not counting the input itself.
O(1) Space — Uses only a few variables, no matter the input size.
def find_max(arr): # O(1) space
maximum = arr[0] # Just one variable
for num in arr:
maximum = max(maximum, num)
return maximum
O(n) Space — Creates a new data structure that scales with input.
def double_all(arr): # O(n) space
result = [] # New list grows to size n
for num in arr:
result.append(num * 2)
return result
O(n²) Space — Creates a 2D structure.
def make_grid(n): # O(n²) space
grid = []
for i in range(n):
row = [0] * n # Each row has n elements
grid.append(row)
return grid # n rows × n cols = n²
The trade-off: Often you can trade space for time (use more memory to run faster) or trade time for space (use less memory but run slower). This is a core concept in DSA!
📋 Instructions
Write a function `analyze_space(func_name)` that returns the space complexity for these functions:
```python
def swap(a, b): # Uses: temp variable
temp = a
a = b
b = temp
def reverse(arr): # Uses: new list of size n
return arr[::-1]
def matrix(n): # Uses: n×n grid
return [[0]*n for _ in range(n)]
```
Return `"O(1)"`, `"O(n)"`, or `"O(n^2)"` for each and print the results.
swap() only uses one extra variable (temp) — that's O(1). reverse() creates a new list the same size as input — O(n). matrix() creates n rows of n elements — O(n²).