Start learning free

LESSON 215 OF 414 · BIG O NOTATION

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

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 (written in pseudo-code, so they apply to any language):

Constant Space Complexity:

function add(a, b):
    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):
    numbers = empty list
    for i from 0 to n - 1:
        add i to the end of numbers
    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):
    numbers = empty list
    for i from 0 to n - 1:
        add an empty list to the end of numbers
        for j from 0 to n - 1:
            add j to the end of the row at index i
    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 its execution (without taking the input values into account).

Space Complexity = Auxiliary Space + Input space

Let's see some examples:

function addAll(arr):
    sum = 0
    for each num in 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

SCALA · BIG O NOTATION

Space Complexity in Scala, explained

What space complexity measures

Space complexity is the amount of memory an algorithm needs, expressed as a function of the input size and written in Big O notation, with the same rules as for time. We ignore constants, so storing three numbers or thirty numbers is still O(1), and only growth with the input matters.

Constant space: O(1)

def sum(a: Int, b: Int): Int = {
  val s = a + b
  s
}

The function uses three numbers: the inputs a and b and the auxiliary value s. That count is fixed no matter what values are passed, so the space is O(1). Scala builds on the JVM, where each call also puts a small frame on the call stack, but a single non-recursive call adds only a constant amount.

Linear space: O(n)

def generate(n: Int): Array[Int] = {
  val numbers = new Array[Int](n)
  for (i <- 0 until n) numbers(i) = i
  numbers
}

The array numbers holds n integers, so memory grows in step with n. generate(5) returns 0,1,2,3,4. Doubling n doubles the memory, which is O(n).

The same holds when the collection is built with higher-order methods. list.map(_ * 2) on a List of n elements creates a second list with n elements, so it uses O(n) extra space. In Scala most collection methods (map, filter, sorted, ++) return a new collection instead of changing the old one, and each of those calls costs space proportional to the result.

Quadratic space: O(n²)

def generate2D(n: Int): Array[Array[Int]] =
  Array.tabulate(n, n)((i, j) => j)

Here the result is a table of n rows and n columns, which is n * n numbers. For n = 3 the rows are all 0,1,2. Memory grows with the square of n, so the space is O(n²).

Auxiliary space versus input space

The memory an algorithm needs splits into two parts:

Space complexity = auxiliary space + input space

  • Input space is the memory that holds the input itself.
  • Auxiliary (extra) space is the temporary memory the algorithm creates while it runs, not counting the input.
def total(arr: Array[Int]): Int = {
  var sum = 0
  for (num <- arr) sum += num
  sum
}

The input array of length n takes O(n) space, but the function only creates two variables, sum and num. Its auxiliary space is O(1). When people ask for an algorithm that "uses O(1) space", they almost always mean auxiliary space. total(Array(1, 2, 3, 4)) returns 10.

Recursion uses space too

Each recursive call adds a frame to the call stack, and the frames stay until the calls return. A recursion that goes n levels deep uses O(n) space even if it creates no arrays:

def depth(n: Int): Int =
  if (n == 0) 0 else 1 + depth(n - 1)

depth(1000) returns 1000, using about a thousand stack frames on the way down. A loop that counts to n uses O(1) space instead. Recursion that is too deep ends the program with a StackOverflowError, so the stack space is a real limit, not just an accounting detail.

Mutating versus copying

An algorithm can often save space by changing data in place. arr.sorted returns a new array (O(n) extra space) and leaves arr unchanged. java.util.Arrays.sort(arr) sorts the array itself instead of returning a copy. After sorting Array(3, 1, 2) both give 1,2,3, but only the first leaves the original as 3,1,2. The trade-off is that changing the input affects every other part of the program that uses the same array.

Common mistakes

  • Counting the input as extra space. If the question is about auxiliary space, the input array does not count.
  • Forgetting the result. A function that returns a new collection of size n uses at least O(n) space for it.
  • Ignoring the call stack. Recursive solutions use stack space proportional to their depth.
  • Treating hidden copies as free. map, filter, slice and ++ each allocate a new collection.

Key takeaways

  • Space complexity measures memory as the input grows, using Big O notation.
  • A fixed number of variables is O(1); a collection of n items is O(n); an n by n table is O(n²).
  • Auxiliary space excludes the input; space complexity includes it.
  • Recursion depth counts towards space.
Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free