Slicing operations in Go - Time & Space Complexity

Time Complexity: Slicing operations

O(1)

Understanding Time Complexity

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

We want to understand how slicing operations affect the program's speed as the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func sliceExample(arr []int) []int {
    newSlice := arr[2:5]
    return newSlice
}
    

This code creates a new slice from an existing slice by selecting elements from index 2 up to 4.

Identify Repeating Operations

• Primary operation: Creating a new slice header pointing to part of the original array.
• How many times: No loops or element copying happens here; it happens once.

How Execution Grows With Input

Creating a slice header is a simple operation that does not copy elements, so the time stays almost the same no matter how big the original slice is.

Input Size (n)	Approx. Operations
10	Constant time, just setting pointers
100	Still constant time, no element copying
1000	Still constant time, no element copying

Pattern observation: The time to create a slice header does not grow with the size of the slice.

Final Time Complexity

Time Complexity: O(1)

This means creating a slice header is very fast and takes the same time regardless of the slice size.

Common Mistake

[X] Wrong: "Creating a slice always copies all elements, so it takes longer for bigger slices."

[OK] Correct: In Go, slicing just creates a new view (header) on the existing array without copying elements, so it is very fast.

Interview Connect

Understanding how slicing works helps you write efficient code and answer questions about data handling speed in Go.

Self-Check

"What if we copied the slice elements into a new slice instead of just slicing? How would the time complexity change?"

Practice

1. In Go, what does the slice expression arr[2:5] do?

easy

A. Extracts elements from index 2 up to and including index 5

B. Extracts elements from index 2 up to but not including index 5

C. Extracts elements from index 3 to 5

D. Extracts elements from index 0 to 5

Solution

1. Step 1: Understand slice indexing in Go

   Go slices include the start index but exclude the end index.

2. Step 2: Apply to arr[2:5]

   This means elements at indexes 2, 3, and 4 are included, but not index 5.

3. Final Answer:

   Extracts elements from index 2 up to but not including index 5 -> Option B

4. Quick Check:

   Slice = arr[2:5] includes indexes 2,3,4 [OK]

Hint: Remember: start included, end excluded in slices [OK]

Common Mistakes:

• Including the end index element
• Confusing start and end indexes
• Thinking slice includes elements before start

2. Which of the following is the correct syntax to slice a Go slice arr from the beginning up to index 4 (excluding 4), omitting the start index?

easy

A. arr[:4]

B. arr[0:4]

C. arr[1:4]

D. arr[4:]

Solution

1. Step 1: Recall slice syntax for start omitted

   Omitting the start index means slicing from the beginning (index 0).

2. Step 2: Check the options

   arr[:4] omits the start index (defaults to 0), slicing up to but excluding index 4. arr[0:4] explicitly includes the start index.

3. Final Answer:

   arr[:4] -> Option A

4. Quick Check:

   Start omitted means from 0 [OK]

Hint: Omit start to slice from beginning: arr[:end] [OK]

Common Mistakes:

• Using arr[1:4] which skips the first element
• Using arr[4:] which slices from index 4 to end
• Confusing start and end indexes

3. What is the output of the following Go code?

arr := []int{10, 20, 30, 40, 50}
slice := arr[1:4]
fmt.Println(slice)

medium

A. [20 30 40 50]

B. [10 20 30 40]

C. [30 40 50]

D. [20 30 40]

Solution

1. Step 1: Identify slice indexes

   The slice arr[1:4] includes elements at indexes 1, 2, and 3.

2. Step 2: Extract elements from arr

   arr[1] = 20, arr[2] = 30, arr[3] = 40, so the slice is [20 30 40].

3. Final Answer:

   [20 30 40] -> Option D

4. Quick Check:

   Slice arr[1:4] = [20 30 40] [OK]

Hint: Slice excludes end index, so last element is arr[3] here [OK]

Common Mistakes:

• Including arr[4] which is 50
• Starting slice at index 0 instead of 1
• Printing the whole array instead of slice

4. Consider this Go code snippet:

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

What is the issue here?

medium

A. The slice will be empty but no error occurs

B. The slice syntax is invalid and causes a compile error

C. The start index is greater than the end index, causing a runtime panic

D. The slice will include elements from index 2 to 3

Solution

1. Step 1: Check slice indexes

   The slice arr[3:2] has start index 3 and end index 2.

2. Step 2: Understand Go slice rules

   In Go, the start index must be less than or equal to the end index; otherwise, it causes a runtime panic.

3. Final Answer:

   The start index is greater than the end index, causing a runtime panic -> Option C

4. Quick Check:

   Start > end in slice causes panic [OK]

Hint: Start index must not exceed end index in slices [OK]

Common Mistakes:

• Assuming slice is empty without error
• Thinking slice syntax is invalid at compile time
• Confusing start and end indexes

5. Given the slice nums := []int{5, 10, 15, 20, 25, 30}, which expression produces a new slice containing only the last three elements?

hard

A. nums[3:]

B. nums[:3]

C. nums[2:5]

D. nums[4:]

Solution

1. Step 1: Identify last three elements indexes

   The last three elements are at indexes 3, 4, and 5 (20, 25, 30).

2. Step 2: Use slice syntax to get from index 3 to end

   Using nums[3:] slices from index 3 to the end, giving [20 25 30].

3. Final Answer:

   nums[3:] -> Option A

4. Quick Check:

   nums[3:] = last three elements [OK]

Hint: Use nums[start:] to slice from start index to end [OK]

Common Mistakes:

• Using nums[:3] which gives first three elements
• Using nums[2:5] which excludes last element
• Using nums[4:] which gives only last two elements