Algorithms from zero

Time and space

Crux Until now, complexity meant time. But every algorithm also costs memory. Learn to measure space complexity — how much extra memory an algorithm uses — and the deliberate tradeoff between time and space.

◷ 18 min

You have learned to measure time complexity: how many steps an algorithm takes as the input grows. But there is another dimension: memory. Every algorithm consumes memory, not just time. Some algorithms are fast but hungry (they remember a lot). Others are slow but thrifty (they remember very little). This lesson teaches you to measure the second dimension: space complexity, the extra memory an algorithm uses. And you will learn the fundamental tradeoff: often you can spend memory to save time, or spend time to save memory.

Goal

After this lesson you can identify and measure space complexity of an algorithm by reading its code, understand the difference between input space and auxiliary space, explain why recursion uses memory (call stack), and recognize a time–space tradeoff and decide which is worth more in context.

The idea

Space complexity measures how much extra memory an algorithm uses as a function of input size n. Just like time complexity, we express space with Big-O notation: O(1), O(n), O(n²), etc.

Auxiliary space is the extra memory the algorithm uses beyond the input itself. When you hear “space complexity”, we almost always mean auxiliary space — the new data structures you create, the variables you declare, the stack frames recursion adds.

Here is the key insight: you can often trade memory for time, or time for memory.

Example 1: Find a duplicate in an array

Nested-loop approach (slow, thrifty):

function hasDuplicate(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) return true;
    }
  }
  return false;
}

Time complexity: O(n²) (nested loops). Space complexity: O(1) (only a couple of variables, i and j).

The algorithm compares every pair of elements, touching each pair once. It is slow but uses almost no extra memory.

Set-based approach (fast, hungry):

function hasDuplicate(numbers) {
  const seen = new Set();
  for (let num of numbers) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

Time complexity: O(n) (one loop, each lookup instant). Space complexity: O(n) (the Set stores up to n values).

The algorithm builds a structure that remembers all the values you have seen. When you encounter a new value, ask “have I seen you before?” — the Set answers instantly. Time falls to linear. Space rises to n.

This is a time–space tradeoff: spend O(n) memory to save O(n²) time. That is a bargain.

Reading space from code:

Count the new data you create:

A few variables (x, y, count) → O(1) (constant space).
A new array of size n → O(n) space.
A new 2D array of size n × n → O(n²) space.
A recursion that calls itself n deep → O(n) stack space.

Recursion is subtle. Each function call reserves stack memory for that call’s variables. If your recursion is n deep, you have n calls on the stack, so O(n) space.

Example: counting down recursively.

function countdown(n) {
  if (n === 0) return;
  console.log(n);
  countdown(n - 1);
}

For countdown(1000), the call stack grows 1000 deep. Each level holds variables (n, the return address). Total: O(n) stack space. If you rewrote this as a loop, the stack stays shallow — O(1) space.

The time–space spectrum:

Most algorithms live somewhere on a spectrum:

O(1) time, O(1) space — rare (simple lookup or check).
O(n) time, O(1) space — thrifty (scan the input, do not remember).
O(n) time, O(n) space — balanced (scan and remember).
O(n²) time, O(1) space — slow but frugal (brute force without help).
O(n log n) time, O(n) space — efficient (merge sort, with extra array).

You cannot always achieve both fast time and low space. Choose wisely based on your constraints. If memory is tight (embedded system, mobile phone), pick the thrifty approach. If speed is critical (real-time system, user waiting for a response), spend memory to accelerate.

The code

Let us see space complexity in real code.

Pattern 1: O(1) space — no new structures

function findMax(numbers) {
  let max = numbers[0];
  for (let i = 1; i < numbers.length; i++) {
    if (numbers[i] > max) max = numbers[i];
  }
  return max;  // Only max and i are new
}

Uses: one variable max, one variable i. Total: O(1) auxiliary space.

Pattern 2: O(n) space — new array or set

function countFrequency(numbers) {
  const freq = new Map();
  for (let num of numbers) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  return freq;  // freq can hold up to n entries
}

Uses: a Map that stores up to n unique values. Total: O(n) auxiliary space.

Pattern 3: O(n) space — recursion depth

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);  // Recursive call adds a stack frame
}

For factorial(1000), the call stack holds 1000 frames (one per level). Total: O(n) stack space.

Pattern 4: O(n²) space — 2D array

function createGrid(n) {
  const grid = [];
  for (let i = 0; i < n; i++) {
    grid[i] = [];
    for (let j = 0; j < n; j++) {
      grid[i][j] = i * j;
    }
  }
  return grid;  // n × n grid
}

Uses: a 2D array of size n × n. Total: O(n²) auxiliary space.

Output

Step-by-step trace

Let us trace the stack growth in a recursive function. Watch how space builds up as we go deeper:


      1
      function countdown(n) {
    

      2
        if (n === 0) return;
    

      3
        console.log(n);
    

      4
        countdown(n - 1);
    

      5
      }

Each level of the stack consumes memory for that function’s variables (n, return address, etc.). With a maximum depth of n, space is O(n).

Complexity

Here is how space complexity affects practical choices:

Algorithm	Time	Space	Use when
Linear search	O(n)	O(1)	Memory is scarce
Binary search	O(log n)	O(1)	Memory is tight; speed is good enough
Hash set lookup	O(n) to build, O(1) per lookup	O(n)	Many lookups; memory is available
Nested-loop duplicate check	O(n²)	O(1)	Array is small or memory is critical
Set-based duplicate check	O(n)	O(n)	Speed matters; memory is plentiful
Merge sort	O(n log n)	O(n)	Speed matters; extra array space is fine
Bubble sort	O(n²)	O(1)	Array is tiny; sorting speed does not matter

Notice the pattern: faster algorithms often use more space. The question is not “which is objectively better?” but “which constraint do I face?” If you have a mobile app with limited RAM, pick O(1) space. If you have a web server with enough memory and users waiting for response, pick fast time.

The trade is real. You cannot have both O(1) space and O(n) time for duplicate detection — you must choose one dimension to sacrifice.

Practice 0 / 5

You have a function that uses a loop to check every element (O(n) time) and only declares a couple of variables (max, i). What is its space complexity?

You create a new array of size n inside your function. What is the space complexity?

A recursive function calls itself n times before returning. What is its stack space complexity?

You want to find a duplicate in an array. The nested-loop approach takes O(n²) time and O(1) space. A set-based approach takes O(n) time and O(n) space. Which is the time–space tradeoff?

You are writing code for an embedded system with 1 MB of RAM. An algorithm with O(n) time and O(n) space will not fit. Which alternative has a chance?

Edge cases

Auxiliary space vs. total space. Some definitions count the input itself as part of space complexity. So they distinguish: total space = input space + auxiliary space. When we say “space complexity” in algorithm courses, we usually mean auxiliary space only — the extra memory you allocate, not the space the input already takes. Know both terms.

Common mistake

Confusing time loops with space. If a function has a loop that runs n times, its time complexity is O(n). But its space complexity is not O(n) unless it allocates something of size n. A loop that runs n times but only uses a couple of variables is O(1) space. Space is about memory structures, not execution steps.

Check yourself

Quiz

Why is the time–space tradeoff important in algorithm design?

Recap

Space complexity measures the extra memory an algorithm uses, written in Big-O notation just like time complexity.

Key points:

Auxiliary space is what we measure — new data structures you create, not the input itself.
Reading space from code: Count the new data. A few variables = O(1). An array of size n = O(n). A 2D array = O(n²). Recursion n deep = O(n) stack space.
The time–space tradeoff: Often you can spend memory to save time (set-based duplicate check) or time to save memory (nested-loop check). Choose based on your constraints.
Common patterns:
- O(1) space: single loop, no new structures
- O(n) space: new array or set, or recursion n deep
- O(n²) space: 2D arrays
In practice: If memory is scarce (embedded systems, mobile), prioritize low space. If speed is critical (servers, real-time systems), prioritize fast time and afford the memory.

Complexity has two dimensions. Mastering both lets you write algorithms that fit your world.

Continue the climb ↑Reading the constraints