Slice length and capacity in Go - Time & Space Complexity

Time Complexity: Slice length and capacity

O(n)

Understanding Time Complexity

When working with slices in Go, it's important to understand how their length and capacity affect performance.

We want to see how operations grow as the slice size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

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

This code appends n items to a slice, growing its length and possibly its capacity.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop runs n times, each time appending one item to the slice.
• How many times: Exactly n times, once per loop iteration.

How Execution Grows With Input

Appending items grows with the number of items n, but capacity changes can cause extra work.

Input Size (n)	Approx. Operations
10	About 10 appends, some may cause capacity increase
100	About 100 appends, with a few capacity increases
1000	About 1000 appends, with several capacity increases

Pattern observation: Most appends are simple, but occasionally the slice grows its capacity, causing extra copying work.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows roughly in direct proportion to the number of items appended.

Common Mistake

[X] Wrong: "Each append always takes the same small amount of time."

[OK] Correct: Sometimes the slice needs to grow its capacity, which involves copying all elements and takes more time.

Interview Connect

Understanding how slice operations scale helps you explain performance in real programs and shows you know how Go manages memory behind the scenes.

Self-Check

What if we pre-allocate the slice with enough capacity before appending? How would the time complexity change?

Practice

1. In Go, what does the len() function return when used on a slice?

easy

A. The maximum number of elements the slice can hold

B. The total memory size of the slice in bytes

C. The index of the last element in the slice

D. The number of elements currently in the slice

Solution

1. Step 1: Understand the purpose of len() on slices

   The len() function returns how many elements are currently stored in the slice.

2. Step 2: Differentiate from capacity

   Capacity is about how many elements the slice can hold before resizing, not the current count.

3. Final Answer:

   The number of elements currently in the slice -> Option D

4. Quick Check:

   len(slice) = current element count [OK]

Hint: Remember: len = current items, cap = max before grow [OK]

Common Mistakes:

• Confusing length with capacity
• Thinking len returns memory size
• Assuming len gives last index

2. Which of the following is the correct way to create a slice with length 3 and capacity 5 in Go?

easy

A. make([]int, 5, 3)

B. make([]int, 3, 5)

C. []int{3, 5}

D. make([]int, 3)

Solution

1. Step 1: Recall the make function signature for slices

   make([]T, length, capacity) creates a slice with given length and capacity.

2. Step 2: Match length and capacity values

   To get length 3 and capacity 5, use make([]int, 3, 5).

3. Final Answer:

   make([]int, 3, 5) -> Option B

4. Quick Check:

   make([]int, length, capacity) [OK]

Hint: make([]T, len, cap) sets length then capacity [OK]

Common Mistakes:

• Swapping length and capacity arguments
• Using slice literal instead of make
• Omitting capacity when needed

3. What will be the output of this Go code?

nums := make([]int, 2, 4)
nums[0] = 10
nums[1] = 20
fmt.Println(len(nums), cap(nums))

medium

A. 2 2

B. 0 4

C. 2 4

D. 4 4

Solution

1. Step 1: Analyze slice creation

   make([]int, 2, 4) creates a slice with length 2 and capacity 4.

2. Step 2: Check length and capacity after assignments

   Assigning values to existing indices does not change length or capacity.

3. Final Answer:

   2 4 -> Option C

4. Quick Check:

   len = 2, cap = 4 [OK]

Hint: Length stays same unless you append beyond capacity [OK]

Common Mistakes:

• Confusing length with capacity
• Assuming capacity equals length after assignment
• Thinking length changes when assigning values

4. Consider this code snippet:

arr := []int{1, 2, 3, 4, 5}
slice := arr[1:3]
fmt.Println(len(slice), cap(slice))

What is the correct output?

medium

A. 2 4

B. 2 2

C. 3 4

D. 3 5

Solution

1. Step 1: Determine length of the slice

   The slice is from index 1 to 3 (exclusive), so length = 3 - 1 = 2.

2. Step 2: Calculate capacity of the slice

   Capacity is from start index to end of original array: 5 - 1 = 4.

3. Final Answer:

   2 4 -> Option A

4. Quick Check:

   len = 2, cap = 4 from slice indices [OK]

Hint: Capacity = original array length - slice start index [OK]

Common Mistakes:

• Using slice length as capacity
• Confusing slice end index with capacity
• Assuming capacity equals original array length

5. You have a slice s := make([]int, 3, 5). You append two elements to it. What will be the length and capacity of s after these appends?

hard

A. Length 5, Capacity 5

B. Length 5, Capacity 10

C. Length 3, Capacity 5

D. Length 5, Capacity 6

Solution

1. Step 1: Understand initial slice size

   Slice s starts with length 3 and capacity 5.

2. Step 2: Append two elements within capacity

   Appending two elements increases length to 5, capacity remains 5 because it is not exceeded.

3. Final Answer:

   Length 5, Capacity 5 -> Option A

4. Quick Check:

   Appending within capacity keeps capacity same [OK]

Hint: Capacity grows only when length exceeds capacity [OK]

Common Mistakes:

• Assuming capacity doubles immediately after append
• Confusing length with capacity after append
• Thinking capacity increases by 1 per append