Best practices in Go - Time & Space Complexity

Time Complexity: Best practices

O(n)

Understanding Time Complexity

When writing Go code, following best practices helps keep programs efficient and easy to understand.

We want to see how these practices affect how fast the program runs as it grows.

Scenario Under Consideration

Analyze the time complexity of the following Go function that finds the first duplicate in a list.

func firstDuplicate(nums []int) int {
    seen := make(map[int]bool)
    for _, num := range nums {
        if seen[num] {
            return num
        }
        seen[num] = true
    }
    return -1
}
    

This code checks each number once and uses a map to track which numbers appeared before.

Identify Repeating Operations

Look for loops or repeated steps in the code.

• Primary operation: Looping through the list once.
• How many times: Once for each number in the list.

How Execution Grows With Input

As the list gets longer, the number of steps grows in a simple way.

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

Pattern observation: The work grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the input list gets bigger.

Common Mistake

[X] Wrong: "Using a map makes the code slower because it adds extra steps inside the loop."

[OK] Correct: The map lets us check for duplicates quickly, so overall the code still only looks at each number once, keeping it fast.

Interview Connect

Understanding how best practices affect time complexity shows you can write code that works well as data grows, a skill valued in many coding challenges.

Self-Check

"What if we replaced the map with a nested loop to check duplicates? How would the time complexity change?"