Map use cases in Go - Time & Space Complexity

Time Complexity: Map use cases

O(n)

Understanding Time Complexity

Maps in Go help us store and find data quickly using keys. Understanding how fast these operations run is important when working with many items.

We want to know how the time to find or add items changes as the map grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func countWords(words []string) map[string]int {
    counts := make(map[string]int)
    for _, word := range words {
        counts[word]++
    }
    return counts
}
    

This code counts how many times each word appears in a list using a map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each word in the list and updating the map.
• How many times: Once for each word in the input list.

How Execution Grows With Input

Each word is processed once, and the map updates happen quickly on average regardless of size.

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

Pattern observation: The work grows directly with the number of words, not more or less.

Final Time Complexity

Time Complexity: O(n)

This means the time to count words grows in a straight line with the number of words.

Common Mistake

[X] Wrong: "Using a map makes the code run in constant time no matter how many words there are."

[OK] Correct: Each word still needs to be processed once, so time grows with the list size, not fixed.

Interview Connect

Knowing how maps work helps you explain efficient data lookups clearly, a useful skill in many coding tasks.

Self-Check

"What if we used a slice instead of a map to count words? How would the time complexity change?"