Space Complexity

When we analyze an algorithm, we don't only care about how much time it takes. We also need to think about how much memory it uses.

Imagine you write a program that works perfectly with 10 numbers. But when you give it 10 million numbers, it needs so much memory that the computer struggles to run it.

This is where space complexity becomes important.

Space complexity describes how much memory an algorithm needs as the input size increases.

Why Do We Need Space Complexity?

Suppose we have an array:

int[] numbers = new int[n];

The larger n becomes, the more memory the array needs.

If:

n = 10

we need space for 10 integers.

If:

n = 1,000,000

we need space for 1 million integers.

So the memory requirement grows with the input size.

We describe this as:

O(n)

This is called linear space complexity.

Time Complexity vs Space Complexity

These two concepts are closely related, but they measure different things.

Time complexity asks:

How much work does the algorithm perform?

Space complexity asks:

How much additional memory does the algorithm need?

For example, consider:

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

The loop runs n times, so its time complexity is:

O(n)

But we're not creating any additional data structure that grows with n.

So its auxiliary space complexity is:

O(1)

This means the extra memory used stays roughly constant.

O(1) — Constant Space

An algorithm has O(1) space complexity when the amount of extra memory it needs doesn't depend on the input size.

For example:

int sum = 0;

for (int i = 0; i < n; i++) {
    sum += i;
}

We only use a few variables:

sum
i

Whether n is 10 or 10 million, we don't create millions of additional variables.

Therefore, the auxiliary space complexity is:

O(1)

O(n) — Linear Space

Now look at this:

int[] numbers = new int[n];

We're creating an array whose size depends directly on n.

If the input size doubles, the required memory also roughly doubles.

Therefore:

O(n)

This is linear space complexity.

Here's another example:

int[] copy = new int[n];

for (int i = 0; i < n; i++) {
    copy[i] = i;
}

The array copy requires space proportional to n.

So the extra space is:

O(n)

O(n²) — Quadratic Space

Sometimes an algorithm creates a two-dimensional structure.

For example:

int[][] matrix = new int[n][n];

If n = 10, the matrix contains:

10 × 10 = 100

elements.

If n = 100, it contains:

100 × 100 = 10,000

elements.

So the required memory grows as:

n²

Therefore, the space complexity is:

O(n²)

Input Space vs Extra Space

There is an important detail when talking about space complexity.

Sometimes the input itself already takes memory.

For example:

int[] numbers = new int[n];

If numbers is the input provided to our algorithm, we don't necessarily consider the input array as extra space.

Instead, we usually focus on the additional memory the algorithm creates while solving the problem.

This is often called auxiliary space.

For example:

int sum = 0;

for (int number : numbers) {
    sum += number;
}

The array numbers is the input.

The algorithm only uses a few extra variables, so the auxiliary space is:

O(1)

This distinction becomes especially useful when analyzing DSA problems.

Space Complexity with a New Array

Consider this example:

int[] numbers = {10, 20, 30, 40, 50};

int[] copy = new int[numbers.length];

for (int i = 0; i < numbers.length; i++) {
    copy[i] = numbers[i];
}

The new copy array grows with the size of the input.

If the input has 5 elements, the copy has 5 elements.

If the input has 1 million elements, the copy has 1 million elements.

So the extra space is:

O(n)

Space Used by Variables

Simple variables usually require constant space.

For example:

int age = 22;
double salary = 50000;
boolean active = true;

The number of variables here doesn't depend on n.

So the space complexity is:

O(1)

Even if the input becomes very large, these variables don't grow with it.

Space Complexity with Loops

A common beginner mistake is thinking that a loop automatically means extra space.

For example:

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

The loop runs n times, but it doesn't store all n values.

It only needs the loop variable i.

So:

Time → O(n)
Space → O(1)

This is a very important difference.

A loop can increase time complexity without increasing space complexity.

Space Complexity with Recursion

Recursion is another place where space complexity becomes important.

Consider:

static void count(int n) {

    if (n == 0) {
        return;
    }

    System.out.println(n);

    count(n - 1);
}

If we call:

count(5);

the calls look roughly like:

count(5)
   ↓
count(4)
   ↓
count(3)
   ↓
count(2)
   ↓
count(1)
   ↓
count(0)

Each recursive call needs memory on the call stack.

If there are n recursive calls, the extra space can become:

O(n)

We'll explore recursion and its complexity in much more detail later.

Time and Space Together

Let's look at an example:

int[] result = new int[n];

for (int i = 0; i < n; i++) {
    result[i] = i * 2;
}

The loop runs n times.

So:

Time Complexity → O(n)

We also create an array containing n elements.

So:

Space Complexity → O(n)

Therefore:

Time  → O(n)
Space → O(n)

Why Space Complexity Matters

Memory is a limited resource.

If an algorithm uses too much memory, it can cause problems such as:

• High memory usage

• Slow performance

• Out-of-memory errors

• Application crashes

Sometimes we can make a program faster by using more memory. Other times, we need to reduce memory usage even if that means doing a little more work.

So when designing an algorithm, we often have to think about both time and space.

A Simple Comparison

Suppose we have two solutions to the same problem.

Algorithm A:

Time  → O(n)
Space → O(1)

Algorithm B:

Time  → O(n)
Space → O(n)

Both take roughly linear time, but Algorithm A uses less additional memory.

If memory usage is important, Algorithm A may be preferable.

But there isn't always one universally "best" solution. Sometimes using extra memory can make an algorithm much faster.

This is called a time-space tradeoff.

Time-Space Tradeoff

Imagine you need to repeatedly search for information.

You could calculate the information every time you need it, which may take more time.

Or you could calculate it once and store the result in a data structure, which uses more memory but allows faster access later.

So sometimes:

More memory → Less time
Less memory  → More time

The right choice depends on the problem.

The Main Idea

Space complexity tells us how the memory requirements of an algorithm grow as the input size increases.

The common complexities you'll see are:

O(1)    → Constant space
O(n)    → Linear space
O(n²)   → Quadratic space

And remember the important distinction:

Time complexity tells us how the amount of work grows, while space complexity tells us how the extra memory usage grows.

When solving DSA problems, don't just ask:

"How fast is my algorithm?"

Also ask:

"How much extra memory does my algorithm need?"

That way, you're thinking about both sides of algorithm efficiency.