Slice and array relationship in Go - Time & Space Complexity

Time Complexity: Slice and array relationship

O(n)

Understanding Time Complexity

When working with slices and arrays in Go, it's important to understand how operations on them affect performance.

We want to know how the time to perform actions grows as the size of the slice or array changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func sumSlice(s []int) int {
    total := 0
    for _, v := range s {
        total += v
    }
    return total
}

This code sums all elements in a slice by looping through each item once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element of the slice.
• How many times: Exactly once per element, so as many times as the slice length.

How Execution Grows With Input

As the slice gets bigger, the number of additions grows directly with its size.

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

Pattern observation: The work grows in a straight line with the number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to sum the slice grows directly with the number of elements.

Common Mistake

[X] Wrong: "Accessing elements in a slice is slow because it copies the whole array each time."

[OK] Correct: A slice points to the original array's data, so accessing elements is fast and does not copy the entire array.

Interview Connect

Understanding how slices relate to arrays and how operations scale helps you write efficient Go code and explain your reasoning clearly.

Self-Check

"What if we changed the slice to an array parameter instead? How would the time complexity change?"