Common slice operations in Go - Time & Space Complexity

Time Complexity: Common slice operations

O(n)

Understanding Time Complexity

When working with slices in Go, it's important to know how the time needed changes as the slice grows.

We want to understand how common slice actions take longer or stay the same as the slice gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Append elements to a slice
func appendElements(slice []int, n int) []int {
    for i := 0; i < n; i++ {
        slice = append(slice, i)
    }
    return slice
}

// Access element by index
func accessElement(slice []int, index int) int {
    return slice[index]
}
    

This code shows two common slice operations: adding elements one by one and accessing an element by its position.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop that appends elements to the slice.
• How many times: The loop runs n times, once for each element added.
• Accessing an element by index happens just once, no repetition.

How Execution Grows With Input

As the number of elements n increases, the time to append grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 append steps
100	About 100 append steps
1000	About 1000 append steps

Accessing an element by index takes the same small amount of time no matter the size.

Pattern observation: Appending grows linearly, accessing stays constant.

Final Time Complexity

Time Complexity: O(n) for appending elements, O(1) for accessing an element.

This means adding many elements takes longer as you add more, but getting one element is always quick.

Common Mistake

[X] Wrong: "Appending one element to a slice always takes the same tiny time no matter what."

[OK] Correct: Sometimes appending triggers the slice to grow its storage, which takes extra time, so appending many elements adds up.

Interview Connect

Understanding how slice operations scale helps you write efficient code and explain your choices clearly in conversations.

Self-Check

"What if we changed the append loop to add elements in batches instead of one by one? How would the time complexity change?"

Practice

1. What does the slice expression mySlice[2:5] do in Go?

easy

A. It returns a new slice containing elements from index 2 up to, but not including, index 5.

B. It returns elements from index 2 to index 5, including index 5.

C. It removes elements from index 2 to 5 from the original slice.

D. It appends elements from index 2 to 5 to the original slice.

Solution

1. Step 1: Understand slice syntax

   The slice expression mySlice[2:5] extracts elements starting at index 2 up to, but not including, index 5. Go slices use half-open intervals, so the element at index 5 is not included in the new slice.

2. Final Answer:

   It returns a new slice containing elements from index 2 up to, but not including, index 5. -> Option A

3. Quick Check:

   Slice[start:end] excludes end index [OK]

Hint: Remember slice end index is excluded in Go slices [OK]

Common Mistakes:

• Including the end index element in the slice
• Thinking slice removes elements from original
• Confusing append with slicing

2. Which of the following is the correct way to append an element 5 to a slice nums in Go?

easy

A. append(nums, 5)

B. nums += 5

C. nums.append(5)

D. nums = append(nums, 5)

Solution

1. Step 1: Recall append function usage

   In Go, append returns a new slice with the element added, so you must assign it back. nums = append(nums, 5) correctly assigns the result back to nums. append(nums, 5) ignores the returned slice. nums.append(5) uses invalid method syntax. nums += 5 is invalid for slices.

2. Final Answer:

   nums = append(nums, 5) -> Option D

3. Quick Check:

   append returns new slice, assign it [OK]

Hint: Always assign append result back to slice variable [OK]

Common Mistakes:

• Not assigning append result back
• Using method syntax like nums.append()
• Trying to add with += operator

3. What is the output of this Go code?

nums := []int{1, 2, 3, 4, 5}
slice := nums[1:4]
slice[0] = 10
fmt.Println(nums)

medium

A. [1 10 3 4 5]

B. [1 2 10 4 5]

C. [10 2 3 4 5]

D. [1 2 3 4 5]

Solution

1. Step 1: Understand slice referencing

   The slice slice := nums[1:4] references the original array elements at indexes 1, 2, and 3. Changing slice[0] to 10 changes nums[1] because slices share the underlying array. Output: [1 10 3 4 5]

2. Final Answer:

   [1 10 3 4 5] -> Option A

3. Quick Check:

   Slices share array, modifying slice changes original [OK]

Hint: Changing slice elements changes original array too [OK]

Common Mistakes:

• Thinking slice is a copy, not a reference
• Modifying wrong index in slice
• Confusing slice length with capacity

4. Identify the error in this Go code snippet:

nums := []int{1, 2, 3}
newSlice := nums[1:4]
fmt.Println(newSlice)

medium

A. Cannot print a slice directly with fmt.Println.

B. Syntax error in slice declaration.

C. Slicing beyond the slice length causes a runtime panic.

D. Missing import for fmt package.

Solution

1. Step 1: Check slice bounds

   The original slice nums has length 3, so valid indices are 0 to 2. Attempting nums[1:4] tries to access index 3 which is out of range, causing a runtime panic.

2. Final Answer:

   Slicing beyond the slice length causes a runtime panic. -> Option C

3. Quick Check:

   Slice end index must be ≤ length [OK]

Hint: Slice end index cannot exceed slice length [OK]

Common Mistakes:

• Assuming slice auto-expands
• Confusing compile error with runtime panic
• Ignoring slice length when slicing

5. Given a slice data := []int{2, 4, 6, 8, 10, 12}, how can you create a new slice containing only the even numbers greater than 6 using slicing and append?

hard

A. newSlice := data[2:5]

B. newSlice := append([]int{}, data[3:]...)

C. newSlice := append(data[:3], data[4:]...)

D. newSlice := data[3:len(data)]

Solution

1. Step 1: Identify elements > 6

   Elements greater than 6 are 8, 10, 12 at indexes 3, 4, 5. Using data[3:] gets these elements. To create a new slice (not referencing original), append to empty slice: newSlice := append([]int{}, data[3:]...).

2. Final Answer:

   newSlice := append([]int{}, data[3:]...) -> Option B

3. Quick Check:

   Slice and append to copy subset [OK]

Hint: Use append to copy slice subset safely [OK]

Common Mistakes:

• Using slice without append copies reference
• Incorrect slice indexes for desired elements
• Trying to remove elements by slicing incorrectly