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?"

Practice

1. What is a slice in Go programming?

easy

A. A flexible, dynamically-sized list of elements.

B. A fixed-size array that cannot change length.

C. A function that slices strings.

D. A type of map with keys and values.

Solution

1. Step 1: Understand slice definition

   A slice in Go is a data structure that holds a list of elements and can grow or shrink in size.

2. Step 2: Compare with other types

   Unlike arrays, slices are dynamic and flexible, unlike maps or functions.

3. Final Answer:

   A flexible, dynamically-sized list of elements. -> Option A

4. Quick Check:

   Slice = dynamic list [OK]

Hint: Remember: slices can grow, arrays cannot [OK]

Common Mistakes:

• Confusing slices with fixed-size arrays
• Thinking slices are functions
• Mixing slices with maps

2. Which of the following is the correct way to create an empty slice of integers in Go?

easy

A. var s []int

B. s := []int{}

C. s := make([]int, 0)

D. All of the above

Solution

1. Step 1: Review slice creation methods

   In Go, you can create an empty slice by declaring a nil slice, using a slice literal with no elements, or using make with length zero.

2. Step 2: Confirm all options are valid

   All three options create an empty slice of integers correctly.

3. Final Answer:

   All of the above -> Option D

4. Quick Check:

   Empty slice creation = D [OK]

Hint: Empty slices can be made in multiple valid ways [OK]

Common Mistakes:

• Using make with negative length
• Confusing array and slice syntax
• Forgetting to initialize slice before use

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

package main
import "fmt"
func main() {
  s := []int{1, 2, 3}
  s = append(s, 4)
  fmt.Println(s)
}

medium

A. [1 2 3]

B. [1 2 3 4]

C. [4]

D. Compilation error

Solution

1. Step 1: Understand initial slice and append

   The slice s starts with elements 1, 2, 3. The append function adds 4 to the end.

2. Step 2: Print the updated slice

   After append, s contains [1 2 3 4], which is printed.

3. Final Answer:

   [1 2 3 4] -> Option B

4. Quick Check:

   append adds element to slice [OK]

Hint: append adds elements to the end of a slice [OK]

Common Mistakes:

• Expecting append to replace elements
• Thinking append returns a new slice without assignment
• Confusing slice with array syntax

4. Identify the error in this Go code snippet:

package main
func main() {
  s := make([]int, 3)
  s[3] = 10
}

medium

A. Slice s is nil

B. Syntax error in make function

C. Index out of range error at s[3]

D. No error, code runs fine

Solution

1. Step 1: Analyze slice length and indexing

   make([]int, 3) creates a slice with length 3, valid indices are 0, 1, 2.

2. Step 2: Check index used in assignment

   Accessing s[3] is out of range and causes a runtime panic.

3. Final Answer:

   Index out of range error at s[3] -> Option C

4. Quick Check:

   Slice indices start at 0, max index = length-1 [OK]

Hint: Slice indices go from 0 to length-1 only [OK]

Common Mistakes:

• Using index equal to slice length
• Confusing slice length and capacity
• Assuming make creates larger slice than specified

5. Given the code below, what will be the length and capacity of slice s after execution?

package main
import "fmt"
func main() {
  s := make([]int, 2, 5)
  s = append(s, 3, 4, 5)
  fmt.Println(len(s), cap(s))
}

hard

A. 5 5

B. 5 10

C. 7 10

D. 3 5

Solution

1. Step 1: Understand make parameters

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

2. Step 2: Append three elements

   Appending 3 elements increases length from 2 to 5, capacity remains 5 as it is enough.

3. Final Answer:

   5 5 -> Option A

4. Quick Check:

   Length grows with append, capacity stays if enough [OK]

Hint: Capacity grows only if append exceeds current capacity [OK]

Common Mistakes:

• Assuming capacity doubles automatically
• Confusing length and capacity
• Forgetting append increases length