Big O notation - Time & Space Complexity - In Go

Calculating time and space complexity is essentially about measuring how your code scales as the amount of data (input size, usually denoted as n) grows. We use Big O Notation to describe this relationship.

Here is a practical guide to calculating complexity, tailored for Go developers.

1. The Golden Rules of Calculation

Before looking at code, keep these three simplification rules in mind. We want the “big picture,” not exact nanoseconds or bytes.

1. Worst Case Rules: Always assume the worst scenario (e.g., the item you are searching for is at the very end of the slice).
2. Drop Constants: O(2n) becomes O(n). O(500) becomes O(1).
3. Drop Non-Dominant Terms: If you have O(n^2 + n), the n^2 grows so much faster that the + n becomes irrelevant. It simplifies to O(n^2).

2. Calculating Time Complexity (Speed)

Time complexity is determined by how many elementary operations the computer performs relative to n. In Go, this usually means looking at loops and recursion.

Constant Time — O(1)

The execution time remains the same regardless of input size.

• Go Context: Accessing a slice by index, map lookups, math operations.

func getFirst(items []int) int {
    return items[0] // Always takes one step, regardless of slice size
}

Linear Time — O(n)

The execution time grows directly in proportion to the input.

• Go Context: A simple for loop or range over a slice/map.

func sum(items []int) int {
    total := 0
    // The loop runs 'n' times
    for _, val := range items {
        total += val
    }
    return total
}

Quadratic Time — O(n^2)

The execution time grows exponentially. This usually happens with nested loops.

• Go Context: Comparing every element in a slice to every other element.

func findDuplicates(items []int) {
    n := len(items)
    // Outer loop runs n times
    for i := 0; i < n; i++ {
        // Inner loop runs n times for EACH outer loop
        for j := 0; j < n; j++ {
            if i != j && items[i] == items[j] {
                fmt.Println("Duplicate found")
            }
        }
    }
    // Total steps = n * n = n^2
}

Logarithmic Time — O(\log n)

The time grows very slowly. This happens when you halve the input at every step.

• Go Context: Binary Search (on sorted slices) or operations on balanced trees.

func binarySearch(items []int, target int) bool {
    low, high := 0, len(items)-1
    
    for low <= high {
        mid := (low + high) / 2 // Cut the problem in half
        if items[mid] == target {
            return true
        }
        if items[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return false
}

3. Calculating Space Complexity (Memory)

Space complexity measures how much additional memory (RAM) is needed relative to the input size.

Note: We generally do not count the space taken by the input itself, only the extra space created by your algorithm.

Constant Space — O(1)

You use a fixed number of variables, regardless of the input size.

// Even if 'items' has 1 million integers, we only create 
// one new variable 'sum' (an int).
func sumSpace(items []int) int {
    sum := 0 
    for _, v := range items {
        sum += v
    }
    return sum
}

Linear Space — O(n)

You create a new data structure that grows with the input.

// We create a NEW slice 'copy' that is the same size as 'items'
func copySlice(items []int) []int {
    copy := make([]int, 0, len(items))
    for _, v := range items {
        copy = append(copy, v)
    }
    return copy
}

The Hidden Space Cost: Recursion

In Go, every function call adds a frame to the “Call Stack”. If you recurse n times, you are using O(n) space, even if you don’t create new variables.

// This uses O(n) space because it keeps n function calls open in memory
func factorial(n int) int {
    if n == 0 { return 1 }
    return n * factorial(n-1)
}

4. Common Go Nuances

When calculating complexity in Go, watch out for these specific behaviors:

Slices and append

• Amortized Time: append is usually O(1). However, if the slice capacity is full, Go must allocate a new, larger array and copy all elements over. This copy operation is O(n).
• Tip: If you know the size beforehand, use make([]int, 0, size) to keep it O(1).

String Concatenation

Strings in Go are immutable.

• The Trap: str += "a" inside a loop creates a new string every time, copying the old contents. This is O(n^2).
• The Fix: Use strings.Builder. It uses an internal buffer, making the operation O(n).

Map Lookups

• Time: Technically O(1) on average, but in worst-case scenarios (hash collisions), it can degrade (though Go’s implementation is robust).
• Space: Maps add significant memory overhead compared to slices due to internal bucket structures.

Summary Table