Start learning free

LESSON 160 OF 348 · BIG O NOTATION

Space Complexity in TypeScript: O(1), O(n) and O(n²)

Reading Read the full explanation

Space Complexity measures the total amount of memory that an algorithm or operation needs to run according to its input size.

Space Complexity is a parallel concept to Time Complexity. We express space complexity measurements using the Big-O notation, following the same guidelines like we do for time complexity.

Now let's learn how to compute space complexity by taking a few examples:

Constant Space Complexity:

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

In the example above, we use 3 number variables: a and b, which are input variables and sum, which is an auxiliary variable.

And because the space requirement is fixed (3 number variables), hence it is called Constant Space Complexity and is noted with O(1).

Linear Space Complexity:

 function generate(n) {
    let numbers = [];
    for (let i = 0; i < n; i++) {
        numbers.push(i);
    }
    return numbers;
}

In the example above, we use an auxiliary array numbers which is populated with n numbers.

Since the total space requirement is n numbers, the Space Complexity is increasing linearly with the increase in the input value n, hence it is called as Linear Space Complexity and is noted with O(n).

Quadratic Space Complexity:

 function generate(n) {
    let numbers = [];
    for (let i = 0; i < n; i++) {
        numbers.push([]);
        for (let j = 0; j < n; j++) {
            numbers[i].push(j);
        }
    }
    return numbers;
}

In the example above, we use an auxiliary 2D array numbers of n rows and n columns.

Since the total space requirement is n^2 numbers, the Space Complexity is directly proportional to the squared of the input value n, hence it is called as Quadratic Space Complexity and is noted with O(n^2).

Extra/Auxiliary Space:

Sometimes Extra/Auxiliary Space is confused with Space Complexity. But Auxiliary Space is the extra space or the temporary space used by the algorithm during it's execution (without taking the input values into account).

Space Complexity = Auxiliary Space + Input space

Let's see some examples:

 function sum(arr) {
    let sum = 0;
    for(let num of arr) {
        sum += num;
    }
    return sum;
}

In the example above, we have an input array arr. If we denote its length by n, the Input Space is O(n).

However, we use only 2 auxiliary variables sum and num, so the Extra Space is O(1).

Next lesson

TYPESCRIPT · BIG O NOTATION

Space Complexity in TypeScript, explained

What space complexity measures

Space complexity measures how much memory an algorithm needs as a function of its input size. It is the companion of time complexity and uses the same Big O notation, with the same rules: describe the growth, ignore constant factors, and keep the dominant term. A function that needs memory for ten values or for twenty values, no matter how large the input is, still has the same space complexity.

In TypeScript the things that take up memory are the variables you declare and the arrays, strings, objects, Maps and Sets you build. Type annotations take no memory at run time: they are erased when the code is compiled to JavaScript. Only the values matter.

Constant space: O(1)

function sum(a: number, b: number): number {
  const total: number = a + b;
  return total;
}

The function holds three numbers: the inputs a and b, and the helper total. Calling it with bigger numbers doesn't change that count, so the space is fixed. This is constant space, written O(1). The word "constant" doesn't mean "one variable"; it means the memory doesn't grow with the input.

Linear space: O(n)

function generate(n: number): number[] {
  const numbers: number[] = [];
  for (let i = 0; i < n; i++) {
    numbers.push(i);
  }
  return numbers;
}

Here the array numbers ends up with n elements, so the memory grows in step with n. Twice the n, twice the memory. That is linear space, O(n). The loop variable i is one more number, but a constant on top of n is dropped.

Quadratic space: O(n²)

function generate(n: number): number[][] {
  const numbers: number[][] = [];
  for (let i = 0; i < n; i++) {
    numbers.push([]);
    for (let j = 0; j < n; j++) {
      numbers[i].push(j);
    }
  }
  return numbers;
}

This builds n rows, each holding n numbers, so n * n values in total. The memory is proportional to the square of n: quadratic space, O(n²). Any grid or table with n rows and n columns costs this much.

Input space and auxiliary space

When people say "space complexity" they sometimes mean different things, so it helps to separate two parts:

  • Input space is the memory taken by the arguments you receive.
  • Auxiliary space (also called extra space) is the additional memory the algorithm uses while it runs, not counting the input.

Space complexity as defined here is their sum. Problems that say "use O(1) extra space" are talking about auxiliary space only.

function sum(arr: number[]): number {
  let total = 0;
  for (const num of arr) {
    total += num;
  }
  return total;
}

The input array has n elements, so the input space is O(n). The function declares only total and num, two numbers regardless of n, so its auxiliary space is O(1). When a problem asks for O(1) extra space, this is the kind of function it wants.

Copying versus changing in place

The difference between auxiliary space O(n) and O(1) is often a question of whether you build a new array or reuse the old one. Reversing an array shows both:

function reverseCopy(arr: number[]): number[] {
  const out: number[] = [];
  for (let i = arr.length - 1; i >= 0; i--) {
    out.push(arr[i]);
  }
  return out;
}

function reverseInPlace(arr: number[]): void {
  let l = 0, r = arr.length - 1;
  while (l < r) {
    const t = arr[l];
    arr[l] = arr[r];
    arr[r] = t;
    l++;
    r--;
  }
}

reverseCopy allocates a second array of n elements, so it uses O(n) extra space and leaves the input as it was. reverseInPlace swaps elements inside the input with a few index variables, so it uses O(1) extra space, but it changes the caller's array. Which one is better depends on whether the caller still needs the original.

Hidden memory

Some memory use isn't visible as a declaration:

  • Recursion. Each active call occupies a stack frame. A function like countDown(n) that calls countDown(n - 1) until n is 0 has n frames alive at the deepest point, so it uses O(n) space even though it declares no array. Very deep recursion can end with a RangeError (stack overflow): with a depth of a million, countDown throws one in Node.
  • Copies. slice, concat, the spread syntax [...arr] and string concatenation all create new values, and the new value's size counts.
  • Collections. A Set or Map that stores up to n entries costs O(n).

Time against space

The two often trade against each other. Remembering the values you have already seen in a Set can turn a quadratic search into a linear one, at the cost of O(n) extra space. When you solve a problem, state both costs: "O(n) time and O(1) extra space".

Common mistakes

  • Counting the input as extra space when the problem asks for auxiliary space, or leaving it out when it asks for total space.
  • Saying a function that returns a new array of size n uses O(1) space because it has few variables. The returned array is memory the function created.
  • Forgetting the call stack in recursive solutions.
  • Believing type annotations use memory. They exist only at compile time.

Key takeaways

  • Space complexity uses Big O to describe how memory grows with the input.
  • A fixed number of variables is O(1); an array of n values is O(n); an n by n grid is O(n²).
  • Space complexity equals input space plus auxiliary space; "extra space" means only the auxiliary part.
  • Recursion depth, copies and collections all count.
Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free