Space Complexity Analysis

Jr Codex DSA Notes

Level: Beginner Prerequisites: Chapter 3 Time to complete: ~20 minutes

Table of Contents

1. What Space Complexity Measures
2. Input Space vs. Auxiliary Space
3. O(1) Auxiliary Space
4. O(n) Auxiliary Space
5. Recursion and Call Stack Space
6. The Time-Space Tradeoff
7. Summary & Next Steps

1. What Space Complexity Measures

Space complexity measures how much extra memory an algorithm needs as input size grows, using the same Big O notation as time complexity. It answers: "If I double the input, roughly how much more memory does this need beyond the input itself?"

2. Input Space vs. Auxiliary Space

• Input space — memory needed to hold the input itself. This is usually not counted, since it exists whether or not you run your algorithm.
• Auxiliary space — extra memory your algorithm allocates on top of the input (new lists, hash maps, recursion stack frames, etc.). This is what "space complexity" almost always refers to.

def double_all(items):
    result = []                 # NEW list — this is auxiliary space
    for item in items:
        result.append(item * 2)
    return result
    # Auxiliary space: O(n) — `result` grows in proportion to `items`

3. O(1) Auxiliary Space

An algorithm that modifies data in place, or only uses a fixed number of extra variables regardless of input size, uses constant auxiliary space:

def double_in_place(items):
    for i in range(len(items)):
        items[i] *= 2           # modifies the existing list, no new structure
    # Auxiliary space: O(1) — no new memory that scales with n

4. O(n) Auxiliary Space

Any time you build a new data structure whose size depends on the input, you have O(n) (or higher) auxiliary space:

def get_unique(items):
    seen = set()               # grows with the number of unique items — O(n)
    result = []                # could grow up to size n — O(n)
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result
    # Auxiliary space: O(n)

This is the tradeoff you saw in Chapter 1's set example — sets often win on time by spending more on space.

5. Recursion and Call Stack Space

Recursive functions use memory for every "in-progress" call sitting on the call stack, even if they don't explicitly create new data structures. This is easy to forget and a frequent interview gotcha (Module 4 covers recursion in depth).

def sum_to_n(n):
    if n == 0:
        return 0
    return n + sum_to_n(n - 1)
    # n unfinished calls sit on the stack at the deepest point — O(n) space,
    # even though no list or dict was ever created

Compare with the iterative version:

def sum_to_n_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total
    # O(1) space — no call stack growth, just one variable

Same time complexity (O(n)), different space complexity — recursion trades space for often-cleaner code, a tradeoff worth naming explicitly whenever you reach for it.

6. The Time-Space Tradeoff

A recurring theme in DSA: you can often make an algorithm faster by using more memory, or use less memory at the cost of speed. Neither is universally "better" — the right choice depends on your constraints:

Fast, more memory:   Store results in a hash map for O(1) lookup → O(n) space
Slow, less memory:   Re-scan the list each time you need a value → O(1) space

You'll see this tradeoff explicitly in Module 8 (Hashing) and Module 10 (Dynamic Programming), where memoization is precisely trading space for time.

7. Summary & Next Steps

Key Takeaways

• Space complexity almost always refers to auxiliary space — extra memory beyond the input itself.
• Building new lists, sets, dicts, or other structures that scale with n gives you O(n) (or higher) space.
• Recursive calls consume call-stack space proportional to recursion depth — this is real space complexity, even without an explicit data structure.
• Time and space can often be traded against each other; neither is "correct" in isolation — it depends on your constraints.

Concept Check

1. What's the difference between input space and auxiliary space?
2. Why does a recursive function that never creates a list or dict still have non-constant space complexity?
3. Give an example of trading memory for speed, and speed for memory.

Next Chapter

→ Chapter 5: Best, Average & Worst Case

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index