Big O: Space Complexity

The space means additional space. This space doesn’t care how much size the input is.

Memory

Heap: store variables we assigned

Stack: keep track of the function calls

What takes memory space?

• Variables

• Data Structures

• Function Call

• Allocations

Example 1:

In the function sayBooooooo, it takes one more space for i := 0. Ignore the size of the input slice num. The space complexity is O(1).

In the function sliceOfHiNTimes, it creates a new slice hiSlice. Then, fill this slice with the string “Hi“ as an item, and each “Hi“ item occupies memory. Follow the Big O rule 2, removing the constants (O(1 + n) —> O(n)). The space complexity is O(n)

package main

import "fmt"

func main() {
    num := []int{1, 2, 3, 4, 5, 6, 7}

    // space complexity: O(1)
    // one more space for i
    sayBooooooo(num)

    // space complexity: O(n)
    sliceOfHiNTimes(7)
}

func sayBooooooo(input []int) {
    for i := 0; i < len(input); i++ {
        fmt.Println("Say booooooo!")
    }
}

func sliceOfHiNTimes(times int) []string {
    // create a new slice
    hiSlice := make([]string, times)

    // fill this slice with loop
    // each item in the slice occupies a memory space
    for i := 0; i < times; i++ {
        hiSlice[i] = "Hi"
    }
    fmt.Println(hiSlice)
    return hiSlice
}

Example 2:

Find a user’s first and last tweet content. The space complexity is O(1).

package main

import "fmt"

func main() {
    // find first tweet and last tweet
    tweets := []string{"hi, this is my first tweet", "great", "holiday"}
    findFirstAndLastTweet(tweets)

}

func findFirstAndLastTweet(tweets []string) {
    firstTweet := tweets[0]            // O(1)
    lastTweet := tweets[len(tweets)-1] // O(1)

    fmt.Println("First tweet:", firstTweet, ",Last tweet:", lastTweet)
}