Engineering Fluency OS

Why This Matters

Speed is not the only resource that matters. Every variable you create, every array you build, every recursive call you make consumes memory. When you process a 10 GB file by loading it all into an array, your program crashes. When your web server allocates a new object for each of 50,000 concurrent requests, it runs out of RAM.

Space complexity measures how much memory an algorithm uses as the input grows. Understanding it lets you choose between a fast solution that uses lots of memory and a slower solution that barely uses any. This tradeoff -- time vs space -- is one of the most fundamental decisions in software engineering.

Define Terms

Visual Model

Input Array[4, 2, 7, 1, 3]

Approach ACreate new array

Approach BModify in place

[3, 1, 7, 2, 4]Copy reversed

Swap ends inwardtemp = arr[0]

O(n) extra space

O(1) extra space

The full process at a glance. Click Start tour to walk through each step.

Auxiliary space is the extra memory an algorithm needs beyond the input itself.

Code Example

Code

// O(n) Space: creates a new reversed array
function reverseNew(arr) {
  const result = [];
  for (let i = arr.length - 1; i >= 0; i--) {
    result.push(arr[i]);
  }
  return result;
}
console.log(reverseNew([1, 2, 3, 4])); // [4, 3, 2, 1]

// O(1) Space: reverses in place by swapping
function reverseInPlace(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    const temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++;
    right--;
  }
  return arr;
}
const a = [1, 2, 3, 4];
reverseInPlace(a);
console.log(a); // [4, 3, 2, 1]

// O(n) Space from recursion (call stack)
function sumRecursive(arr, i = 0) {
  if (i >= arr.length) return 0;
  return arr[i] + sumRecursive(arr, i + 1);
}
console.log(sumRecursive([1, 2, 3, 4])); // 10
// Each call adds a frame to the stack: n frames = O(n) space

// O(1) Space iterative version
function sumIterative(arr) {
  let total = 0;
  for (const num of arr) {
    total += num;
  }
  return total;
}
console.log(sumIterative([1, 2, 3, 4])); // 10

Interactive Experiment

Try these exercises:

Write two versions of a function that returns only even numbers from an array: one that creates a new array (O(n) space) and one that modifies the original (O(1) auxiliary space).
Write a recursive Fibonacci function. How many stack frames does fib(10) create? What about fib(50)?
Convert the recursive Fibonacci to an iterative version that uses only two variables. Compare the space usage.
Create a function that builds a 2D matrix of size n x n. What is the space complexity?

Quick Quiz

Coding Challenge

Remove Duplicates In Place

Write a function `removeDuplicates` that takes a SORTED array of numbers and removes duplicates IN PLACE, returning the count of unique elements. The first k elements of the array should contain the unique values. Do not create a new array -- modify the input array and use O(1) extra space. Hint: use two pointers -- one for reading and one for writing.

Loading editor...

Real-World Usage

Space complexity decisions shape real systems:

Mobile apps: Phones have limited RAM. Loading a 50,000-row dataset into memory crashes the app. Pagination and streaming process data in constant space.
Embedded systems: IoT devices and microcontrollers may have only a few KB of RAM. In-place algorithms are mandatory.
Big data processing: MapReduce and streaming frameworks process terabytes by never holding the full dataset in memory at once.
Caching: Caches trade space for time -- storing precomputed results uses memory to avoid recomputation. Choosing what to cache is a space-time tradeoff.
Database indexes: An index speeds up queries (O(log n) time) but consumes disk space proportional to the data (O(n) space).

Space Complexity