Slice creation in Go - Time & Space Complexity

Time Complexity: Slice creation

O(n)

Understanding Time Complexity

When we create slices in Go, it's important to know how the time it takes grows as the slice size grows.

We want to understand how the work changes when we make bigger slices.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

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

This code creates a slice of size n and fills it with numbers from 0 to n-1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for loop that assigns values to each element in the slice.
• How many times: The loop runs exactly n times, once for each element.

How Execution Grows With Input

As the slice size n grows, the number of assignments grows at the same rate.

Input Size (n)	Approx. Operations
10	10 assignments
100	100 assignments
1000	1000 assignments

Pattern observation: The work grows directly with the size of the slice.

Final Time Complexity

Time Complexity: O(n)

This means the time to create and fill the slice grows in a straight line with the slice size.

Common Mistake

[X] Wrong: "Creating a slice is instant and does not depend on size."

[OK] Correct: Even though the slice header is small, filling the slice with values requires work for each element, so time grows with size.

Interview Connect

Understanding how slice creation scales helps you reason about performance when working with lists or arrays in Go, a common task in many programs.

Self-Check

"What if we used append in a loop instead of make and direct assignment? How would the time complexity change?"