Appending to slices in Go - Time & Space Complexity

Time Complexity: Appending to slices

O(n)

Understanding Time Complexity

When we add items to a slice in Go, the time it takes can change depending on how many items are already there.

We want to understand how the time to append grows as the slice gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

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

This code adds numbers from 0 up to n-1 to a slice one by one.

Identify Repeating Operations

• Primary operation: The append operation inside the loop.
• How many times: It runs exactly n times, once for each number added.

How Execution Grows With Input

Each append usually adds one item, but sometimes the slice needs to grow its storage, which takes extra time.

Input Size (n)	Approx. Operations
10	About 10 appends, with a few extra steps for growing storage
100	About 100 appends, with some extra steps for growing storage
1000	About 1000 appends, with a few more extra steps for growing storage

Pattern observation: The total work grows roughly in a straight line with n, because growing the slice happens only a few times.

Final Time Complexity

Time Complexity: O(n)

This means the time to append n items grows roughly in direct proportion to n.

Common Mistake

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

[OK] Correct: Sometimes the slice needs to grow its storage, which takes extra time, so not every append is equally fast.

Interview Connect

Understanding how appending to slices works helps you explain how data structures grow and perform in real programs.

Self-Check

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

Practice

1. What does the append function do in Go when used with slices?

easy

A. It adds new elements to the end of a slice, returning the updated slice.

B. It removes elements from the beginning of a slice.

C. It sorts the elements of a slice in ascending order.

D. It copies elements from one slice to another without changing size.

Solution

1. Step 1: Understand the purpose of append

   The append function is designed to add elements to the end of a slice in Go.

2. Step 2: Recognize the return value

   Append returns a new slice that includes the original elements plus the added ones.

3. Final Answer:

   It adds new elements to the end of a slice, returning the updated slice. -> Option A

4. Quick Check:

   append adds elements to slice end = A [OK]

Hint: Append adds elements at the end and returns the new slice [OK]

Common Mistakes:

• Thinking append removes elements
• Assuming append sorts the slice
• Not realizing append returns a new slice

2. Which of the following is the correct way to append the integer 5 to a slice named nums?

easy

A. nums.append(5)

B. append(nums, 5)

C. nums = append(nums, 5)

D. nums += 5

Solution

1. Step 1: Recall append syntax in Go

   Append returns a new slice, so you must assign it back to the original slice variable.

2. Step 2: Check each option

   nums = append(nums, 5) correctly assigns the result of append back to nums. Options A, B, and D don't work correctly.

3. Final Answer:

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

4. Quick Check:

   Assign append result back to slice = C [OK]

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

Common Mistakes:

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

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

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

medium

A. [1 2 3]

B. Compilation error

C. [4 5]

D. [1 2 3 4 5]

Solution

1. Step 1: Understand initial slice and append

   nums starts as [1, 2, 3]. Append adds 4 and 5 to the end.

2. Step 2: Result after append

   After append, nums becomes [1, 2, 3, 4, 5]. Printing nums shows this full slice.

3. Final Answer:

   [1 2 3 4 5] -> Option D

4. Quick Check:

   Appending multiple elements adds all to slice end = D [OK]

Hint: Append can add multiple elements at once [OK]

Common Mistakes:

• Expecting append to replace elements
• Thinking append returns only new elements
• Confusing slice initialization syntax

4. Identify the error in this Go code snippet:

var letters []string
append(letters, "a")
fmt.Println(letters)

medium

A. append result is not assigned back to letters

B. letters slice is nil and cannot be appended to

C. Syntax error in append function call

D. fmt.Println cannot print slices

Solution

1. Step 1: Check slice initialization

   letters is a nil slice but append can still add elements to it.

2. Step 2: Check append usage

   Append returns a new slice; the code does not assign this back to letters, so letters remains nil.

3. Final Answer:

   append result is not assigned back to letters -> Option A

4. Quick Check:

   Always assign append result back to slice = B [OK]

Hint: Assign append result to slice even if slice is nil [OK]

Common Mistakes:

• Assuming append modifies slice in place
• Thinking nil slice cannot be appended to
• Believing fmt.Println can't print slices

5. Given a slice data := []int{1, 2, 3}, which code snippet correctly appends all elements from another slice extra := []int{4, 5, 6} to data?

hard

A. data = append(data, &extra...)

B. data = append(data, extra...)

C. data = append(data, extra)

D. data = append(data, *extra)

Solution

1. Step 1: Understand appending slices

   To append all elements of one slice to another, use the ... operator to unpack elements.

2. Step 2: Analyze options

   data = append(data, extra...) correctly uses append with extra unpacked as extra.... Options B, C, and D have syntax errors or incorrect usage.

3. Final Answer:

   data = append(data, extra...) -> Option B

4. Quick Check:

   Use ... to append all slice elements = A [OK]

Hint: Use ... to unpack slice elements when appending [OK]

Common Mistakes:

• Trying to append slice without ... (adds slice as single element)
• Using pointer or dereference incorrectly
• Trying to append slice as single element