Address and dereference operators in Go - Time & Space Complexity

Time Complexity: Address and dereference operators

O(n)

Understanding Time Complexity

When using address and dereference operators in Go, it's important to see how accessing values through pointers affects the program's speed.

We want to know how the time to access or change data grows as we work with more elements.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func incrementAll(nums []int) {
    for i := 0; i < len(nums); i++ {
        p := &nums[i]  // get address
        *p = *p + 1     // dereference and increment
    }
}

This code loops through a list of numbers, uses the address operator to get each element's location, then uses dereference to increase its value by one.

Identify Repeating Operations

• Primary operation: Looping through each element in the slice and accessing it via pointer.
• How many times: Exactly once for each element in the input slice.

How Execution Grows With Input

As the number of elements grows, the number of pointer accesses and increments grows at the same rate.

Input Size (n)	Approx. Operations
10	10 increments and pointer accesses
100	100 increments and pointer accesses
1000	1000 increments and pointer accesses

Pattern observation: The work grows directly with the number of elements, so doubling elements doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the task grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Using pointers makes the code run faster and changes the time complexity."

[OK] Correct: Using pointers changes how you access data but does not reduce the number of operations needed to process each element.

Interview Connect

Understanding how pointer operations scale helps you explain memory access patterns clearly and shows you grasp how low-level details affect program speed.

Self-Check

"What if we replaced the loop with recursion to increment elements? How would the time complexity change?"