ReviseAlgo Logo

Foundations

Space Complexity

Understand memory usage in algorithms, auxiliary space trade-offs, and call stack memory.

Last Updated: July 31, 2026 • 15 min read

1. Introduction

What is Space Complexity?

Space Complexity measures how much memory (RAM) an algorithm needs to run to completion as the input size (N) grows.

Auxiliary Space vs Total Space

  • Input Space: Memory occupied by the input data itself (e.g. an array of N integers passed into a function).
  • Auxiliary Space: Extra memory created by the algorithm to solve the problem (new arrays, hash sets, variables, call stack).

    • In coding interviews, Space Complexity usually refers to Auxiliary Space.

    Where is it Used?

  • Mobile & Embedded Systems: Smartwatches, IoT devices, and smartphones have strict RAM constraints (e.g., avoiding Out-Of-Memory crashes).
  • Big Data Processing: Processing a 500 GB log file on a server with 16 GB of RAM requires stream processing in O(1) auxiliary space.

    • 2. Mental Model

    Imagine a Chef Preparing a Salad.

    Both approaches produce the same chopped salad! But Approach 1 leaves your kitchen counter clean, whereas Approach 2 clutter your kitchen counter with extra dishes. Space complexity counts those extra dishes.

    3. Concept: Sources of Extra Memory

    When your code runs, memory is consumed in two primary places:

    1. Variables & Primitive Data Types (O(1) Space)

    Storing a few counters or index pointers requires constant extra space:

    This is O(1) Auxiliary Space because memory does not depend on input size N.

    2. Dynamically Allocated Data Structures (O(N) Space)

    Creating a copy array or a HashSet to store N elements:

    This requires O(N) Auxiliary Space.

    3. Recursive Call Stack (O(N) or O(log N) Space)

    Every time a function calls itself recursively, a new stack frame is pushed onto the call stack storing parameter variables and return addresses.

    A recursion depth of N calls takes O(N) Call Stack Space.

    4. Visuals

    Common Space Complexity Ratings

    Auxiliary SpaceDescriptionCode ExampleMemory Impact
    O(1)Constant SpaceIn-place array swap, counter variables🟢 Minimal (Bytes)
    O(log N)Logarithmic SpaceCall stack depth of Binary Search or balanced Tree🟢 Low
    O(N)Linear SpaceCreating a copy array, HashMap, or linear recursion🟡 Moderate
    O(N²)Quadratic SpaceCreating an N × N 2D grid matrix🔴 High

    5. Real-World Examples

  • Mobile Web Browsers: Chrome on mobile limits memory per tab. Algorithms with O(1) memory prevent app force-closures when scrolling long feeds.
  • Image Processing Applications: In-place image filters (flipping pixels in the existing buffer) use O(1) extra RAM, whereas filters that clone high-resolution 4K bitmap images use O(Width × Height) memory.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers will often push for space optimization: "You solved this in O(N) space using a HashMap. Can you solve it in O(1) space in-place?"

    Common Mistakes

    Warning: 1. Forgetting Recursion Call Stack: Claiming a recursive function uses O(1) space because no arrays were created, ignoring the O(N) stack frames!
    > 2. Confusing Input Space with Auxiliary Space: Counting the input array size as part of the algorithm's memory footprint when the interviewer only asked for extra space.
    > 3. String Concatenation Memory: Forgetting that strings are immutable in Java/Python. Appending chars in a loop creates O(N²) garbage objects!

    Important Interviewer Tips

  • Mention space complexity alongside time complexity (e.g. "Time is O(N) and auxiliary space is O(1)").
  • In-place modifications are prized by interviewers when memory is constrained.

    • 7. Summary

  • Auxiliary Space measures the extra memory your algorithm creates.
  • Primitives & Pointers take O(1) space.
  • HashMaps, Sets, Copy Arrays take O(N) space.
  • Recursion depth adds call stack memory proportional to maximum recursion depth.

    • 8. Quiz

    Question 1: What is the difference between Input Space and Auxiliary Space? Answer: Input space is the memory needed to store the input data itself. Auxiliary space is the extra memory allocated by the algorithm to perform its calculations.
    Question 2: Does an algorithm that sorts an array in-place without creating new arrays use O(1) auxiliary space? Answer: Yes, because modifying elements within the existing array structure requires only a few index variables, keeping extra space constant O(1).
    Question 3: If a function calls itself recursively N times before reaching the base case, what is its space complexity? Answer: O(N) space complexity due to N recursive call stack frames held simultaneously in memory.
    Question 4: What is the auxiliary space complexity of creating a 2D matrix of size N x N? Answer: O(N²) space complexity, because N x N memory cells are allocated in the heap.
    Question 5: Why is using StringBuilder better than string concatenation (+) inside a loop in Java? Answer: StringBuilder modifies memory in-place, taking O(N) space. Using (+) repeatedly creates N new immutable string objects in memory, wasting extra RAM.