Start learning free

LESSON 160 OF 348 · BIG O NOTATION

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

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

KOTLIN · BIG O NOTATION

Space Complexity in Kotlin, explained

What space complexity measures

Space complexity measures how much memory an algorithm needs as a function of its input size. Like time complexity, it is written in Big O notation and ignores constant factors: an algorithm that stores 3n numbers and one that stores n numbers are both O(n).

It is useful to split the total into two parts:

  • Input space: the memory the input itself takes, such as an array of n elements.
  • Auxiliary space: the extra memory the algorithm allocates while it runs, not counting the input.

Space complexity is the sum of the two. Many problems state their limit as "extra space", and then only the auxiliary part counts. A function that reads an array of n numbers and uses a few variables has O(n) input space but only O(1) extra space.

Constant space: O(1)

The memory stays the same no matter how large the input is.

fun sum(a: Int, b: Int): Int {
    val total = a + b
    return total
}

The function holds three Int values: the parameters a and b, and the local total. That number is fixed, so the space is O(1). Calling sum(2, 3) returns 5.

Linear space: O(n)

The memory grows in proportion to the input.

fun generate(n: Int): List<Int> {
    val numbers = mutableListOf<Int>()
    for (i in 0 until n) {
        numbers.add(i)
    }
    return numbers
}

The list ends up with n numbers, so the space is O(n). generate(5) returns [0, 1, 2, 3, 4]. Notice that the input here is just the number n, and the memory depends on its value. A size can come from a value as well as from a collection's length.

Quadratic space: O(n²)

A table with n rows and n columns holds n * n numbers.

fun generateGrid(n: Int): List<List<Int>> {
    val numbers = mutableListOf<MutableList<Int>>()
    for (i in 0 until n) {
        numbers.add(mutableListOf())
        for (j in 0 until n) {
            numbers[i].add(j)
        }
    }
    return numbers
}

For n = 3 the result is [[0, 1, 2], [0, 1, 2], [0, 1, 2]]: nine numbers. In general the space is O(n²). Doubling n makes the grid four times as large.

Input space versus auxiliary space

fun sumAll(arr: IntArray): Int {
    var total = 0
    for (num in arr) {
        total += num
    }
    return total
}

The array arr holds n elements, so the input space is O(n). The function adds only two variables, total and num, so the auxiliary space is O(1). Calling sumAll(intArrayOf(4, 5, 6)) returns 15. When a problem asks for O(1) extra space, this is the kind of solution it wants.

Kotlin details that affect space

Copies versus in-place changes

Some operations change the array you pass; others return a new one. With val a = intArrayOf(3, 1, 2):

  • a.sortedArray() returns a new sorted array, [1, 2, 3], and leaves a as [3, 1, 2]. It uses O(n) extra space.
  • a.sort() sorts a itself, and afterwards a holds [1, 2, 3]. It adds no extra array of size n.

The sorting method sorted() on a list, and functions such as map, filter, reversed and toList, also build new collections, each O(n). Check which kind of call you are using when a problem limits the extra space.

Strings are immutable

A Kotlin String can't be edited. Every "change", such as s + "x" or s.substring(1), creates a new string. Building a result in a StringBuilder keeps one buffer that grows to the final length, which is O(n) space.

Recursion uses the call stack

Each active function call keeps its variables on the call stack, and that memory counts as auxiliary space. A recursive function that goes n calls deep uses O(n) space, even if it creates no list at all:

fun sumRecursive(n: Int): Long = if (n == 0) 0L else n + sumRecursive(n - 1)

sumRecursive(1000) returns 500500, with 1001 calls waiting on the stack at the deepest point. The stack has a limited size, so a very deep recursion fails: calling sumRecursive(10_000_000) throws a StackOverflowError. The loop version of the same sum, like sumAll, needs only O(1) space.

How to compute it

  1. List what the algorithm allocates: new variables, lists, arrays, maps, strings and copies.
  2. Decide how each one grows with the input. A fixed number of variables is O(1). A collection that gets one element per input element is O(n).
  3. Add the recursion depth if the function calls itself.
  4. Keep the largest term and drop constants. Allocations that exist at different times don't add up if the earlier ones are no longer in use, but the safe way to count is the most memory held at one moment.
  5. State whether you include the input. Say "extra space" when you don't.

Common mistakes

  • Counting the input as extra space. A function that only reads an array of n numbers doesn't use O(n) extra space.
  • Forgetting the output. The list returned by generate is the point of the function. Whether the output counts depends on the problem's rules, so read them.
  • Ignoring hidden copies. Slicing, sortedArray, map and string joins all allocate O(n) memory.
  • Ignoring the stack. Recursion that looks free still costs space in proportion to its depth.

Key takeaways

  • Space complexity is the memory an algorithm needs as the input grows. Auxiliary space is the extra part, without the input.
  • A fixed set of variables is O(1); one element stored per input element is O(n); an n by n table is O(n²).
  • In Kotlin, in-place calls such as sort() save space, while sortedArray(), map and string concatenation create copies.
  • Recursion depth counts as space because of the call stack.
Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free