Space Complexity: Memory Space is Just as Important as Speed

Chris successfully optimized his code using the Time Complexity (O) concept he learned last time. He drastically increased speed by reducing 2.5 billion operations to just 100,000.

"It's perfect! The speed is flying now."

However, a few days after deployment, a strange report came in from a user.

"If I leave the shopping mall tab open, Chrome eats up 2GB of memory, and eventually, the tab dies with an 'Aw, Snap!' error."

The speed improved, but this time Memory (RAM) was the issue. To find data quickly, Chris had created excessively large objects or dived too deep into recursive functions, exceeding the browser's memory limit.

Algorithm performance is evaluated not only by Speed (Time) but also by Space (Memory). This is Space Complexity.

1. What is Space Complexity?

If Time Complexity asks, "How much longer does it take as data increases?",

Space Complexity asks, "How much more memory does it occupy as data increases?"

The code we write consumes space in two main ways:

When discussing algorithm performance, the core focus is usually on how much Auxiliary Space is used.

2. Variables are Light: O(1)

This is the most efficient space complexity. Even if the input data is 1 million items, the additional space used is just a few variables.

// ✅ Space Complexity O(1)
function sum(arr) {
  let total = 0; // One variable (Number type)
  
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]; // Reusing existing space
  }
  
  return total;
}

No matter how large arr becomes, we only need two extra variables: total and i. The memory efficiency is excellent.

3. Copies Make it Heavy: O(N)

This occurs when space is needed in proportion to the input data. It usually happens when copying an array or creating a new array to store results.

// ⚠️ Space Complexity O(N)
function double(arr) {
  const newArr = []; // Requires new space equal to input(arr)
  
  for (let i = 0; i < arr.length; i++) {
    newArr.push(arr[i] * 2);
  }
  
  return newArr;
}

If arr is 100MB, newArr also takes up 100MB. Memory usage doubles in an instant. JavaScript's map, filter, and slice all return new arrays, so their space complexity is O(N).

Note: In JavaScript, Strings are Immutable. Every time you add (+) or slice a string, a new memory space is allocated. Keep in mind that string manipulation can also consume O(N) space.

4. The Hidden Cost: Recursion's Stack Memory

This is the part Chris likely missed. It's when memory explodes even though no large variables were declared.

// ❌ Space Complexity O(N) - Recursive Call
function countdown(n) {
  if (n <= 0) return;
  console.log(n);
  countdown(n - 1); // Calls itself
}

countdown(50000); // Maximum call stack size exceeded

When a function calls another function without finishing, the computer records the location to return to in a memory space called the 'Call Stack'.

If the recursion deepens by N levels, the stack memory also accumulates N frames.

Therefore, recursive functions consume O(N) space behind the scenes, even if there are no visible variables in the code. To solve this, you must change recursion to Loops (for, while). Loops do not build up the stack, so their space complexity is O(1).

5. The Trade-off: Trading Time and Space

An interesting point is that Time Complexity and Space Complexity often have an Inverse Relationship (Trade-off).

Remember the Set Chris used in the first post?

He used additional memory (O(N) space) to create the Set, but in exchange, he gained search speed (O(1) time).

Modern development environments have ample RAM, so we usually choose to sacrifice a little memory to increase speed. However, in mobile environments or large-scale data processing, memory conservation is essential.

Key Takeaways

Now you possess both weapons: Time and Space.

Finally, let's combine all this knowledge and practice analyzing code in the real world, saying, "This is O(N) and that is O(1)."

Continuing in the next post: "Expressing Code in Big-O Notation: Solving Real-World Examples."

🔗 References