Start learning free

LESSON 160 OF 338 · BIG O NOTATION

Space Complexity in Go: 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

GO · BIG O NOTATION

Space Complexity in Go, explained

What space complexity measures

Space complexity describes how much memory an algorithm needs as its input grows. Like time complexity, it is written in Big O notation and ignores constant factors. An algorithm that needs a fixed handful of variables is O(1). One that needs memory proportional to the input size n is O(n).

Two quantities are easy to mix up:

  • Input space is the memory the input itself occupies, for example a slice of n integers.
  • Auxiliary space (extra space) is the additional memory the algorithm allocates while it runs, not counting the input.

Space complexity is the sum of the two. In practice, when people compare algorithms, they usually talk about auxiliary space, because the input is the same for every algorithm that solves the problem. Interview answers such as "O(1) extra space" mean the auxiliary part.

Constant space: O(1)

func sum(a, b int) int {
    total := a + b
    return total
}

The function uses the parameters a and b and one local variable, total. The number of variables doesn't depend on the values passed in, so the space is O(1). Every int takes the same 8 bytes here, however large its value is.

Linear space: O(n)

func generate(n int) []int {
    numbers := []int{}
    for i := 0; i < n; i++ {
        numbers = append(numbers, i)
    }
    return numbers
}

The slice numbers ends up with n elements, so memory grows in step with n: O(n). Calling generate(5) returns [0 1 2 3 4].

A Go detail: append sometimes allocates a bigger backing array and copies the elements across, so for a moment the old and the new array both exist. The capacity grows by a constant factor each time, so the total is still proportional to n. The space complexity stays O(n).

Quadratic space: O(n²)

func generate(n int) [][]int {
    numbers := make([][]int, n)
    for i := 0; i < n; i++ {
        numbers[i] = make([]int, n)
        for j := 0; j < n; j++ {
            numbers[i][j] = j
        }
    }
    return numbers
}

This builds an n by n table: n rows, each a slice of n integers. That is n * n numbers, so the space is O(n²). For n = 3 it returns [[0 1 2] [0 1 2] [0 1 2]].

The first make creates the outer slice with n empty rows (each is nil). Each iteration then gives one row its own slice of n integers. A Go slice of slices doesn't build the rows for you.

Input space against auxiliary space

func sum(arr []int) int {
    total := 0
    for _, num := range arr {
        total += num
    }
    return total
}

If arr has n elements, the input space is O(n). The function itself adds only two variables, total and num, so the auxiliary space is O(1). Because space complexity is input plus auxiliary space, the total is O(n) + O(1), which is O(n). When someone says this function "uses O(1) space", they mean the extra space.

Slices are passed as small headers

In Go, passing a slice to a function copies only the slice header: a pointer to the elements, a length and a capacity. The elements themselves are not copied. So passing a slice of a million integers costs a constant amount of extra memory, and the callee can change the caller's elements:

func reverseInPlace(arr []int) {
    for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
        arr[i], arr[j] = arr[j], arr[i]
    }
}

This reverses a slice with O(1) auxiliary space. After reverseInPlace on [1 2 3 4], the caller's slice holds [4 3 2 1]. A version that builds a second slice and returns it uses O(n) auxiliary space but leaves the original untouched. That trade between memory and safety comes up often.

The call stack counts too

Memory isn't only variables you declare. Every function call needs a stack frame, and a recursive function that goes n calls deep holds n frames at once:

func depth(n int) int {
    if n == 0 {
        return 0
    }
    return 1 + depth(n-1)
}

The function allocates no slices, yet depth(1000) has 1,000 calls waiting on each other at the deepest point. Its space is O(n). A loop doing the same job would be O(1). Go grows its stacks on demand, so deep recursion rarely fails quickly, but the memory is still used.

Common mistakes

  • Forgetting hidden allocations. Building a new slice, string or map of size proportional to the input adds O(n). Converting a string with []rune(s) or []byte(s) makes a copy, and that copy is O(n) too.
  • Counting the input as extra. A function that only reads its parameters and keeps a few counters is O(1) auxiliary space, even though the input is large.
  • Treating a loop as memory. A loop that runs n times but only reuses the same few variables is still O(1) space. Time and space are separate questions.
  • Ignoring recursion depth. A recursive solution may be O(n) in space even when it creates no data structure.

Key takeaways

  • Space complexity is the memory an algorithm needs as a function of the input size, written in Big O.
  • A fixed number of variables is O(1). A slice that grows with the input is O(n). A grid of n by n is O(n²).
  • Space complexity is input space plus auxiliary space; comparisons usually look at the auxiliary part.
  • Slices are shared by header, so passing them is cheap and changing their elements affects the caller.
  • Recursion depth uses stack memory and counts toward the total.
Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free