Space Complexity & Trade-offs

Every algorithm trades time for space, learn to navigate that trade-off

Big O applies to two resources: time (operations) and space (memory).
Space complexity measures how much extra memory an algorithm uses relative to its input. We care because memory is finite, a beautiful O(1) time solution is worthless if it needs O(2ⁿ) memory.

📱In the Real World...

A smartphone has ~8GB RAM. An algorithm that stores O(n!) results for n=20 would need 2.4 petabytes. No amount of RAM would save you.

Same goal, different space usagepython

# O(n) space, stores all results
def running_totals(nums):
    totals = []          # grows with n
    running = 0
    for n in nums:
        running += n
        totals.append(running)
    return totals

# O(1) space, just needs current total
def final_total(nums):
    running = 0          # one variable, always
    for n in nums:
        running += n
    return running

# Trade-off: if you need ALL totals → use O(n)
# If you only need the final value → O(1) wins

Extra list = O(n) space⚠ Works but messy

# O(n) space: stores all n numbers
def reverse_list(nums):
    result = []
    for i in range(len(nums)-1, -1, -1):
        result.append(nums[i])
    return result

Two pointers = O(1) space✓ Pythonic

# O(1) space: swaps in-place
def reverse_list(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

💡

Both are O(n) time, but the second uses O(1) space, trading allocation for swaps

🤔Quick Check

A function creates a list of n elements. What is its space complexity?

🎯

Phase Complete!

Complexity & Thinking

You understand Big O for both time and space, and you can spot the dominant complexity in code. Ready to explore data structures?

0/500

Practice Exercises

0/1 solved

Exercise 1 of 1easy

⏱ 00:00

Measure Space Usage

Complete count_unique to return the count of unique numbers. Aim for O(n) time and O(n) space.
Expected output: 3

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next