Blog 5: Space Complexity Explained (Memory Matters Too)

Introduction

In the previous blog, we learned how fast an algorithm runs (Time Complexity).

Now the next question is:

How much memory does your solution use?

Because in real-world systems, memory is limited.

👉 This is where Space Complexity comes in.

⚡ What is Space Complexity?

Space Complexity measures:

How much memory an algorithm uses as input size grows

It includes:

• Variables
• Data structures
• Function calls

🧊 Simple Intuition

Think of it like packing a bag 🎒

• Fewer items → less space
• More items → more space

👉 Same logic applies to programs

📦 Types of Space

1. Input Space

• Memory used by input itself
• Usually not counted in optimization

2. Auxiliary Space (Important)

Extra memory used by your algorithm

👉 This is what we focus on

📊 Basic Examples

🔹 O(1) — Constant Space

function sum(a, b) {
  return a + b;
}

👉 Uses only a few variables → constant memory

🔹 O(n) — Linear Space

function copyArray(arr) {
  let newArr = [];

  for (let i = 0; i < arr.length; i++) {
    newArr.push(arr[i]);
  }

  return newArr;
}

👉 New array grows with input → O(n)

📉 Visual Growth Comparison (Space)

Input Size (n) →
--------------------------------------------------------------

O(1)     
→  ●────────●────────●────────●  
   memory stays same (few variables only)

O(n)     
→  ●────●────────●──────────●  
   memory grows with input size (extra array/list)

🔁 Hidden Space (Very Important)

Even if you don’t create arrays…

👉 Recursion uses memory internally

function countDown(n) {
  if (n === 0) return;

  countDown(n - 1);
}

👉 Each call adds to call stack

countDown(3)
→ countDown(2)
→ countDown(1)
→ countDown(0)

👉 Space Complexity: O(n)

⚖️ Time vs Space Trade-Off

Sometimes you can:

• Use more memory → faster solution
• Use less memory → slower solution

Example:

• HashMap → fast lookup, more memory
• Loop search → less memory, slower

⚠️ Common Mistakes

❌ Ignoring space completely

Only focusing on time

❌ Missing recursion stack

Thinking no extra memory is used

❌ Unnecessary data structures

Creating extra arrays without need

🎯 Interview Insight

Interviewers don’t just check correctness.

They often ask:

“Can you reduce space complexity?”

This means:

• Are you using extra memory unnecessarily?
• Can you solve the same problem without extra arrays or data structures?

Example

❌ Approach 1 (O(n) space)

function doubleArray(arr) {
  let result = [];

  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }

  return result;
}

👉 Extra array created → O(n) space

✅ Approach 2 (O(1) space)

function doubleArray(arr) {
  for (let i = 0; i < arr.length; i++) {
    arr[i] = arr[i] * 2;
  }

  return arr;
}

👉 Modified in-place → O(1) space

🎯 Key Insight

If you avoid extra storage and modify existing data → space reduces

⚖️ Follow-up Interview Question

“Can you solve it in O(1) space?”

This means:

• Use no extra memory
• Only a few variables allowed

👉 This is called in-place solution

Quick Practice

Code:

function printItems(n) {
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
}

What is Space Complexity?

Let’s break it:

• i → one variable
• No array, no extra storage
• Loop runs many times, but memory does NOT increase

Final Answer:

O(1) — Constant Space

⚠️ Important Understanding

Loop running n times ≠ O(n) space

Because:

• Time is increasing
• Memory is NOT increasing

Golden Rule

Time Complexity depends on how many steps run.
Space Complexity depends on how much extra memory is used.

🚀 What’s Next?

Now that you understand both:

• Time Complexity
• Space Complexity

Next blog:

“Linear Search vs Binary Search (Complete Understanding)”

✍️ Closing Thought

“Efficient code is not just fast — it also uses memory wisely.”